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