Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần mặc định. Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mặc định.

Bessie đang làm một bài kiểm tra đúng/sai gồm \(N\) câu (\(1\le N\le 2\cdot 10^5\)). Với câu hỏi thứ \(i\), cô nhận được \(a_i\) điểm nếu trả lời đúng, mất \(b_i\) điểm nếu trả lời sai, hoặc không được cũng không mất điểm nếu không trả lời (\(0<a_i,b_i\le 10^9\)).

Bessie biết tất cả đáp án vì cô là một cô bò thông minh, nhưng lo rằng Elsie (người coi thi) sẽ thay đổi hồi tố không quá \(k\) câu hỏi sau bài kiểm tra sao cho Bessie không trả lời đúng những câu đó.

Cho \(Q\) (\(1\le Q\le N+1\)) giá trị ứng viên của \(k\) (\(0\le k\le N\)), hãy xác định số điểm Bessie có thể đảm bảo với mỗi \(k\), biết rằng cô phải trả lời ít nhất \(k\) câu hỏi.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(a_i\) và \(b_i\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một giá trị \(k\). Không giá trị \(k\) nào xuất hiện quá một lần.

Dữ liệu ra

In đáp án cho mỗi \(k\) trên một dòng riêng.

Ví dụ

2 3
3 1
4 2
2
1
0

-3
1
7

Phân nhóm

• Dữ liệu 2–4: \(N\le 100\).
• Dữ liệu 5–7: \(Q\le 10\), \(N\le 2\cdot 10^5\).
• Dữ liệu 7–20: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Platinum — True or False Test. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1502