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