모든 것의 지배자

당신은 갑자기 과대망상적인 성향이 생겨 명성을 갈망하게 되었다. 동영상 플랫폼 Dutub에서 팔로워를 $K$명 이상 얻고 싶다. 이를 위해 동영상 아이디어 $N$개를 구상했다. 뛰어난 지적 능력 덕분에 각 동영상을 게시했을 때 팔로워 수가 어떻게 변할지 정확히 알고 있다. 각 동영상에는 $a$와 $b$라는 두 매개변수가 있다. 현재 팔로워가 $f$명일 때 동영상을 게시하면, 이후 팔로워 수는 $a \cdot f + b$이 된다. 처음에는 팔로워가 $0$명이다.

가능한 한 빨리 목표를 달성하기 위해, 적어도 $K$명의 팔로워를 얻는 데 필요한 최소 개수의 동영상을 게시하려 한다. 선택한 동영상은 어떤 순서로든 게시할 수 있지만, 각 동영상은 최대 한 번만 게시할 수 있다.

당신은 참을성이 없어서 $K$에 대한 생각을 바꿀 수도 있다. 따라서 서로 다른 $K$의 값 $Q$개에 대해 필요한 동영상의 최소 개수를 구해야 한다.

채점

당신의 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 한 테스트 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$2$| $Q \leq 5, N \leq 10$

$2$ |$13$| $Q \leq 5, N \leq 20$

$3$ |$20$| $Q \leq 5, N \leq 1000$

$4$ |$25$| $Q \leq 5$

$5$ |$20$| $Q \leq 1000$

$6$ |$20$| 추가 제한 조건 없음.

입력의 첫째 줄에는 동영상 아이디어의 수와 고려하려는 팔로워 수의 개수를 나타내는 정수 $N$와 $Q$가 주어진다 ($1 \le N, Q \le 2 \cdot 10^5$).

이어지는 $N$개의 줄에는 동영상 아이디어가 주어진다. 각 줄에는 위에서 설명한 의미를 갖는 두 정수 $a$와 $b$이 주어진다 ($1 \leq a, b \leq 10^5$).

마지막 줄에는 고려하려는 서로 다른 팔로워 수인 $Q$개의 정수 $K_1, K_2, \dots, K_Q$가 주어진다 ($1 \leq K_i \leq 8 \cdot 10^9$).

각 $K_i$에 대해, 적어도 $K_i$명의 팔로워를 얻기 위해 게시해야 하는 동영상의 최소 개수를 출력한다. 주어진 동영상 아이디어로 팔로워 $K_i$명을 얻는 것이 불가능하다면, 대신 $-1$을 출력한다. 이 답들을 모두 한 줄에 출력한다.

첫 번째 예제에서는 최대 9명의 팔로워를 얻을 수 있다.

두 번째 예제의 첫 번째 질문에서는 두 $(1,100)$ 동영상을 모두 게시하여 팔로워 200명을 얻을 수 있다. 팔로워 1006명을 얻으려면 먼저 $(1,100)$ 동영상을 게시하고, 그다음 $(2,1)$ 동영상 중 하나를 게시한 뒤, 마지막으로 $(5,1)$ 동영상을 게시하여 3개의 동영상으로 팔로워 $((0 \cdot 1 + 100) \cdot 2 + 1) \cdot 5 + 1= 1006$명을 얻을 수 있다. 3개의 동영상을 사용해서는 팔로워를 $1006$명보다 많이 얻을 수 없다.

세 번째 예제에서 가능한 가장 많은 팔로워 수는 동영상을 $(2,20)$, $(3,7)$, $(5,2)$ 순서로 게시하여 얻을 수 있으며, 그 수는 $((0 \cdot 2 + 20) \cdot 3 + 7) \cdot 5 + 2=337$명이다. 어떤 순서로도 이보다 많은 팔로워를 얻을 수 없으므로, $338$명을 얻는 것은 불가능하다.