Поликарп хочет приготовить суп. Чтобы это сделать, ему нужно купить ровно \(n\) литров воды.
В ближайшем магазине есть бутылки с водой только двух типов — \(1\)-литровые бутылки и \(2\)-литровые бутылки. В магазине есть бесконечно много бутылок этих двух типов.
Бутылка первого типа стоит \(a\) бурлей, а бутылка второго типа стоит \(b\) бурлей соответственно.
Поликарп хочет потратить минимально возможное количество денег. Ваша задача — найти минимальное количество денег (в бурлях), которое нужно Поликарпу для того, чтобы купить ровно \(n\) литров воды в ближайшем магазине, если бутылка первого типа стоит \(a\) бурлей, а бутылка второго типа стоит \(b\) бурлей.
Вам также необходимо ответить на \(q\) независимых запросов.
Выходные данные
Выведите \(q\) целых чисел. \(i\)-е число должно быть равно минимальному количеству денег (в бурлях), необходимому Поликарпу для того, чтобы купить ровно \(n_i\) литров воды в ближайшем магазине, если бутылка первого типа стоит \(a_i\) бурлей, а бутылка второго типа стоит \(b_i\) бурлей.