Diana cần bạn giúp tối đa hóa số vàng cô ấy nhận được khi chơi trò chơi yêu thích của mình. Cô ấy thường gặp phải tình huống đứng gần trụ của mình và đối mặt với \(N\) quái vật. Khi đó, Diana và trụ thay phiên nhau bắn các quái vật, và Diana được đi trước. Trong lượt của mình, Diana có thể chọn một quái vật để bắn (điều này có nghĩa là Diana có thể chọn bỏ qua một lượt). Trong lượt của nó, trụ sẽ bắn vào quái vật gần nó nhất. Diana và trụ không thể bắn vào những quái vật đã chết.

Nếu Diana bắn vào một con quái vật, lượng máu của nó sẽ giảm đi \(P\). Nếu trụ bắn vào một con quái vật, lượng máu của nó sẽ giảm đi \(Q\). Nếu máu của quái vật giảm xuống dưới \(1\), nó sẽ bị tiêu diệt. Con quái vật thứ \(i\) bắt đầu với \(H_i\) máu. Diana được thưởng \(G_i\) vàng nếu phát bắn của cô ấy tiêu diệt được con quái vật thứ \(i\), nhưng không nhận được gì nếu phát bắn của trụ tiêu diệt nó. Số vàng tối đa mà Diana có thể nhận được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách đại diện cho \(P\), \(Q\) và \(N\). \(N\) dòng tiếp theo, với dòng thứ \(i\) chứa hai số nguyên cách nhau bởi dấu cách đại diện cho \(H_i\) và \(G_i\).

Các quái vật được cho theo thứ tự khoảng cách của chúng so với trụ. Nói cách khác, trụ sẽ chỉ bắn vào con quái vật thứ \(i\) nếu tất cả các quái vật \(< i\) đã chết.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số vàng tối đa mà Diana có thể nhận được.

Ràng buộc

• \(1 \le T \le 100\)
• \(20 \le P \le 200\)
• \(20 \le Q \le 200\)
• \(1 \le H_i \le 200\)
• \(0 \le G_i \le 10^6\)

Phân nhóm

• Small dataset: \(1 \le N \le 4\).
• Large dataset: \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
20 40 3
100 100
20 100
60 100
20 60 3
80 100
80 200
120 300

Case #1: 300
Case #2: 500

Nguồn

Google Code Jam 2014, Vòng 3, bài Last Hit.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.