True or False Test

문제

Bessie is taking an $NN$-question true or false test ($1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$). For the $ii$-th question, she will gain $a_{i}a\_i$ points if she gets it correct, lose $b_{i}b\_i$ points if she gets it incorrect, or remain even if she does not answer it ().

Bessie knows all the answers because she is a smart cow, but worries that Elsie (who is administering the test) will retroactively change up to $kk$ of the questions after the test such that Bessie does not get those questions correct.

Given $QQ$ ($1\le Q\le N+11\backslash le\; Q\backslash le\; N+1$) candidate values of $kk$ ($0\le k\le N0\backslash le\; k\backslash le\; N$), determine the number of points Bessie can guarantee for each $kk$, given that she must answer at least $kk$ questions.

입력

The first line contains $NN$ and $QQ$.

The next $NN$ lines each contain $a_{i}a\_i$ and $b_{i}b\_i$.

The next $QQ$ lines each contain a value of $kk$. No value of $kk$ appears more than once.

출력

The answer for each $kk$ on a separate line.

2 3
3 1
4 2
2
1
0

-3
1
7