**Замечание: Время на тест для этой задачи 3сек, в 1.5 большее чем по умолчанию.
Память на тест для этой задачи 512MB, в два раза больше чем по умолчанию.**
Беси проходит тест вида да/нет из \(N\) вопросов (\(1\le N\le 2\cdot 10^5\)).
За \(i\)-ый вопрос она может добавить \(a_i\) баллов если ответит правильно,
и отнять \(b_i\) баллов, если ответит неправильно или не изменить сумму, если
не ответит вообще на вопрос (\(0<a_i,b_i\le 10^9\)).
Беси знает ответы на все вопросы, но боится, что администратор теста Эльза
подменит до \(k\) вопросов так, чтоб получилось, что Беси ответила неправильно.
Заданы \(Q\) (\(1\le Q\le N+1\)) кандидатов величин \(k\) (\(0\le k\le N\)),
определите количество баллов, которые Беси гарантированы для каждого \(k\),
зная, что она должна ответить не менее чем на \(k\) вопросов.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(Q\).
Каждая из следующих \(N\) строк содержит \(a_i\) и \(b_i\).
Каждая из следующих \(Q\) строк содержит значение \(k\).
Ни одно из значений \(k\) не появится более одного раза.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите ответ для каждого \(k\) на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
3 1
4 2
2
1
0
|
-3
1
7
|