Một đoạn đường thẳng có N trạm, người ta muốn đặt các đèn tại một số trạm để có thể chiếu sáng được tất cả các trạm . Trên thị trường có M loại đèn, loại thứ i có giá là Ti và có khả năng chiếu sáng với bán kính Ri. Một trạm được đặt đèn i thì nó có khả năng chiếu sáng cho chính nó và các trạm ở bên trái và bên phải nếu khoảng cách từ trạm đặt đèn tới các trạm bên trái và bên phải nhỏ hơn hoặc bằng Ri.
Công việc của bạn là lập trình tìm cách mua các đèn và đặt vào một số trạm để cho tất cả các trạm đều được chiếu sáng với ít tiền nhất.
Dữ liệu: Vào từ file văn bản CHIEUSANG.INP có dạng:
Dòng thứ nhất là hai số N, M (N ≤ 10000, M ≤ 10).
Dòng thứ 2 chứa 2 nguyên là giá tiền và khả năng chiếu sáng của đèn thứ 1,…, dòng thứ M+1 là giá tiền và khả năng chiếu sáng của đèn thứ M. Như vậy M dòng kế tiếp, mỗi dòng chứa hai số nguyên dương. Dòng thứ i+1 là giá tiền Ti và khả năng chiếu sáng Ri của đèn thứ i. (Ti ≤ 30000, Ri ≤ 109).
Dòng thứ M+2 có một số nguyên dương - là toạ độ của trạm thứ 1,…, dòng thứ M+N+1 có một số nguyên dương – là toạ độ của trạm thứ N. Như vậy, N dòng tiếp theo, mỗi dòng một số nguyên dương mô tả vị trí (toạ độ) của N trạm. Dòng thứ i+M+1 chứa giá trị di là toạ độ của trạm thứ i (0 ≤ di ≤ 109).
Trong ví dụ bên dưới: dòng thứ nhất là N=6 trạm, M=2 loại đèn; dòng thứ 2 là giá tiền và khả năng chiếu sáng của loại đèn thứ nhất, dòng thứ 3 là giá tiền và khả năng chiếu sáng của loại đèn thứ hai; 6 dòng tiếp theo là toạ độ của 6 trạm.
Kết quả: Đưa ra file văn bản CHIEUSANG.OUT có dạng:
Dòng thứ nhất gồm hai số nguyên: số thứ nhất là số tiền ít nhất và số thứ 2 là số đèn W cần dựng.
W dòng tiếp theo, mỗi dòng hai số là tên trạm và loại đèn đặt tại trạm đó.
Ví dụ :
| CHIEUSANG.INP | CHIEUSANG.OUT | Giải thích |
|---|---|---|
| 6 2 2 1 100 10 1 2 3 10 20 30 |
8 4 2 1 4 1 5 1 6 1 |
Số tiền ít nhất là 8, cần dựng 4 đèn tại các trạm 2, 4, 5, 6 và chỉ sử dụng loại đèn thứ 1 |
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?