Управление водными шлюзами
У плотины имеется n водосбросов, которые можно использовать для выпуска воды при необходимости. Каждый водосброс обладает своей пропускной способностью, водным путем и затрагивает определенные области ниже по течению. Эти области могут подвергаться риску наводнения, когда водосброс открыт. Потенциальный ущерб, вызванный водосбросом, оценивается числом, которое рассчитывается на основе количества людей и областей, которые могут пострадать.
Предположим, что водосброс G_i имеет объемный расход F_i м³/час и стоимость ущерба C_i. В определенной ситуации плотина содержит объем V м³ воды, который необходимо сбросить в течение T часов. Ваша задача — управлять открытием водосбросов так, чтобы избавиться как минимум от указанного объема воды за ограниченное время при минимальных затратах на ущерб.
Например, у плотины есть 4 водосброса, и их характеристики приведены в следующей таблице.
Случай 1: Необходимо сбросить воду объемом 5 миллионов м³ в течение 7 часов. Минимальная стоимость составит 120,000, если оставить водосброс G_1 открытым на 7 часов.
Случай 2: Необходимо сбросить воду объемом 5 миллионов м³ в течение 30 часов. Минимальная стоимость составит 110,000, если оставить водосбросы G_2 и G_3 открытыми, например, G_2 открыт на 29 часов, а G_3 открыт на 28 часов.
Обратите внимание, что каждый водосброс независим и может быть открыт только на целое количество часов (без дробных частей часа).
Входные данные
Первая строка содержит целое число n, указывающее количество водосбросов (1 ≤ n ≤ 20). Затем следующие n строк содержат по два целых числа: F_i и C_i, которые соответствуют расходу (м³/час) и стоимости ущерба водосброса G_i соответственно. Следующая строка содержит число m, которое является количеством тестовых случаев (1 ≤ m ≤ 50). Следующие m строк содержат по два целых числа: V и T, которые соответствуют объему (м³) воды, которую необходимо сбросить в течение T часов.
1 ≤ F_i, V, C_i ≤ 10^9, 1 ≤ T ≤ 1000
Выходные данные
Для каждого тестового случая выведите минимальную стоимость в точном формате, как показано в примере вывода ниже. Если невозможно сбросить воду объемом V в течение T часов из плотины, выведите "IMPOSSIBLE" (без кавычек).