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