Послухай пісню#4363
Фікрет-мурахоїд освоївся в одній з соціальних мереж. Але спілкується він досить незвичайно. Замість компліментів та усього іншого він шле своїй любій єхидні Кейт пісні. Вони давно знайомі, тому Фікрет віртуозно розбирається в її музичних смаках. Для кожної пісні відомі дві характеристики: її тривалість t_i та задоволення x_i, яке Кейт отримає, прослухавши пісню повністю.
Зараз у Кейт є рівно одиниць вільного часу. Знаючи список наявних у Фікрета пісень, порахуйте, яке максимальне задоволення він може доставити Кейт. Жодні дві чи більше пісень не повинні прослуховуватися одночасно. Перемикання між піснями відбувається автоматично та без пауз.
У першому рядку задається кількість наявних пісень (0 \leq n \leq 100). Кожен з наступних рядків містить цілих числа: t_i (1 \leq t_i \leq 1000) та x_i (-1000 \leq x_i \leq 1000). Далі подається кількість тестових випадків (1 \leq Q \leq 10^5), і кожен з наступних рядків містить по одному цілому числу (1 \leq T \leq 10^4).
Для кожного з запитів у окремому рядку виведіть максимальне задоволення, яке Кейт може отримати.
Приклад 1