문제
Bessie는 N문항의 OX(참/거짓) 시험을 치릅니다 (1 ≤ N ≤ 2⋅10⁵). i번째 문제에서 정답을 맞추면 aᵢ 점을 얻고, 오답이면 bᵢ 점을 감점하며, 답을 포기하면 점수 변화는 없습니다 (0 < aᵢ, bᵢ ≤ 10⁹).
Bessie는 모든 문제의 정답을 알고 있지만, 시험을 주관하는 Elsie가 시험이 끝난 후 최대 k개의 문제를 골라 Bessie의 답안을 “바꿀” 수 있어, 그 문제들에 대해 Bessie가 오답 처리될 위험이 있습니다.
각 후보 k (0 ≤ k ≤ N)에 대해, Bessie는 최소 k문항은 반드시 답해야 합니다. Elsie는 Bessie가 답한 문제 중 최대 k개를 마음대로 “바꿀” 수 있으므로, Bessie가 답한 모든 문제에 대해 최악의 경우, k개의 문제는 오답으로 처리되고 나머지는 정답으로 처리됩니다.
문제의 목표는 Bessie가 어떠한 전략(답할 문제 선택)을 사용하더라도 보장받을 수 있는 최소 점수를 최대화하는 것입니다.
문제에서 주어진 상황에서는 모든 문제에 답하는 것이 최적임이 증명됩니다. 이 경우, 각 문제 i에 대해 Bessie가 원래 얻을 점수는 aᵢ이고, 만약 Elsie가 그 문제를 바꾼다면 Bessie는 –bᵢ의 점수를 받게 됩니다. 따라서 문제 i에 대해 “위험 부담”은 (aᵢ + bᵢ)이며, Elsie는 Bessie에게 최대 피해를 주기 위해, 답한 문제 중 (aᵢ + bᵢ)가 큰 문제들을 선택하여 k개를 바꿀 것입니다.
결과적으로, 모든 문제에 답했을 때의 보장 점수는
총 점수 = (∑₁⁽ᴺ⁾ aᵢ) − (합계: (aᵢ+bᵢ)가 큰 문제 k개)
가 됩니다.
입력
첫 번째 줄에 두 정수 N와 Q가 주어집니다. (Q는 후보 k의 개수로, 1 ≤ Q ≤ N+1)
이후 N개의 줄 각각에 두 정수 aᵢ와 bᵢ (각각 0 < aᵢ, bᵢ ≤ 10⁹)가 주어집니다.
그 다음 Q개의 줄 각각에는 후보 k (0 ≤ k ≤ N)가 한 줄에 하나씩 주어집니다. 각 k는 서로 다릅니다.
출력
각 후보 k에 대해 보장받을 수 있는 최소 점수를 한 줄에 하나씩 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | |
| #3 | 50점 | 추가 제약 조건 없음 |
예제1
2 3
3 1
4 2
2
1
0
-3
1
7