Active Preparation for the Battle

Carnage wants to fight Venom, but first he needs to build up his strength. He learned that eating certain people has a positive effect on symbiote abilities, and the stronger and more capable the person, the more useful they are to eat. However, people tend to resist. A person who is quick enough may raise an alarm before they are dealt with, drawing the attention of the police and Detective Patrick Mulligan.

Carnage's strength $P$ is currently 1, the police suspect nothing, and their alert level $C$ is 0. Carnage can reach $n$ people, and the $i$-th person is described by a pair $(p_i, c_i)$. When Carnage attempts to eat the $i$-th person, one of two things happens:

• If $P \geq p_i$, Carnage is strong enough to deal with the victim silently, and his strength increases by $p_i$ without raising the police alert level.
• Otherwise, the person is still eaten (and $P$ increases by $p_i$), but the police alert level increases by $c_i$.

Carnage can hunt only one target at a time, and each person can be eaten at most once. Carnage chooses the order in which he hunts the victims.

Carnage does not know how dangerous Venom is, so he makes $q$ assumptions about Venom's strength. The $i$-th assumption is a potential strength $x_i$ for Venom. For each assumption, find the minimum police alert level that can result when Carnage reaches strength $P \geq x_i$, or determine that such strength cannot be reached.

The first line contains two integers $n$ and $q$, the number of potential victims and the number of Carnage's assumptions about Venom's strength ($1 \leq n \leq 10^5$; $1 \leq q \leq 10^6$).

Each of the next $n$ lines describes a person. The $i$-th line contains two integers $p_i$ and $c_i$ separated by a space: the strength level of the $i$-th person and the potential increase in police attention when hunting them ($1 \leq p_i \leq 10^9$; $1 \leq c_i \leq 10^9$).

The next line contains $q$ integers $x_1, x_2, \ldots, x_q$ separated by spaces. $x_i$ describes Carnage's $i$-th assumption about Venom's strength ($1 \leq x_i \leq 10^9$). Carnage's memory sometimes fails him, so the same value may appear several times in this sequence.

Print $q$ numbers separated by spaces. The $i$-th number is the answer for the $i$-th assumption. If it is impossible to gather strength at least $x_i$, the answer is $-1$. Otherwise, the answer is the minimum police alert level after Carnage gathers that strength.