전투를 위한 적극적인 준비

카니지는 베놈과 싸우고 싶어 하지만, 그 전에 힘을 길러야 한다. 특정 사람을 잡아먹으면 심비오트의 능력에 좋은 영향을 준다는 사실을 알았고, 사람이 강하고 능력이 있을수록 잡아먹었을 때 얻는 이득도 크다. 하지만 사람은 저항하기 마련이어서, 충분히 날랜 사람은 죽기 전에 소리를 질러 경찰과 형사 패트릭 멀리건의 주의를 끌 수 있다.

현재 카니지의 힘 $P$는 1이고, 경찰은 아무것도 의심하지 않아서 경계 수준 $C$는 0이다. 카니지가 노릴 수 있는 사람은 $n$명이며, $i$번째 사람은 $(p_i, c_i)$ 쌍으로 나타낸다. $i$번째 사람을 잡아먹으려고 하면 다음 두 가지 중 하나가 일어난다.

• $P \geq p_i$이면 카니지는 소리 없이 처리할 수 있고, 힘이 $p_i$만큼 늘어나며 경찰의 경계 수준은 오르지 않는다.
• 그렇지 않으면 사람은 그래도 잡아먹히고(힘은 $p_i$만큼 늘어난다), 경찰의 경계 수준이 $c_i$만큼 오른다.

한 번에 한 명만 사냥할 수 있고, 각 사람은 최대 한 번만 잡아먹을 수 있다. 사냥 순서는 카니지가 정한다.

카니지는 베놈의 힘에 대해 $q$가지 가정을 세운다. $i$번째 가정은 베놈의 힘이 $x_i$일 수 있다는 것이다. 각 가정에 대해, 카니지의 힘이 $P \geq x_i$가 되도록 힘을 모을 때 나올 수 있는 경계 수준의 최솟값을 구하라. 그런 힘을 모을 수 없으면 $-1$을 출력한다.

첫 줄에 정수 $n$과 $q$가 주어진다. $n$은 잡아먹을 수 있는 잠재적 희생자의 수, $q$는 베놈의 힘에 대한 카니지의 가정 수다($1 \leq n \leq 10^5$; $1 \leq q \leq 10^6$).

다음 $n$개 줄에는 사람들에 대한 설명이 주어진다. $i$번째 줄에는 공백으로 구분된 두 정수 $p_i$와 $c_i$가 있으며, 각각 $i$번째 사람의 힘 수준과 그를 사냥할 때 경찰의 주의가 늘어나는 잠재적 증가량이다($1 \leq p_i \leq 10^9$; $1 \leq c_i \leq 10^9$).

다음 줄에는 공백으로 구분된 $q$개의 정수 $x_1, x_2, \ldots, x_q$가 있다. $x_i$는 카니지의 $i$번째 가정에서 베놈의 힘을 나타낸다($1 \leq x_i \leq 10^9$). 카니지의 기억력은 가끔 믿을 수 없어서, 같은 값이 여러 번 나올 수 있다.

공백으로 구분하여 $q$개의 수를 출력하라. $i$번째 수는 $i$번째 가정에 대한 답이다. 힘을 $x_i$ 이상으로 모을 수 없으면 답은 $-1$이고, 그렇지 않으면 그 힘을 모은 뒤 경찰 경계 수준의 최솟값이다.