Nhiệm vụ
Đề bài
Mô tả
Để thư giãn trước khi thi ICPC World Finals, bạn quyết định chơi một trò chơi máy tính tên là Quests (Nhiệm vụ). Bạn đã chơi nó nhiều lần rồi, và giờ bạn muốn có một lượt chơi hoàn hảo, để chuẩn bị cho một kỳ thi chung kết hoàn hảo!
Trong trò chơi, bạn phải hoàn thành một số nhiệm vụ, và mỗi nhiệm vụ hoàn thành mang lại cho bạn một lượng điểm kinh nghiệm (XP). Tổng số XP bạn đã kiếm được tại mỗi thời điểm quyết định cấp độ hiện tại của bạn: cứ mỗi XP kiếm được, bạn lên thêm một cấp. Chính xác hơn, cấp độ của bạn tại một thời điểm là số nguyên lớn nhất sao cho bạn có ít nhất XP.
Mỗi nhiệm vụ có một số XP và một cấp độ khuyến nghị . Nếu bạn hoàn thành nhiệm vụ khi cấp độ của bạn ít nhất là , bạn nhận được XP. Còn nếu bạn hoàn thành nhiệm vụ khi cấp độ của bạn nhỏ hơn , bạn nhận được XP. Hằng số là hệ số nhân XP, tạo ra phần thưởng cho việc hoàn thành nhiệm vụ khi bạn ở cấp độ thấp hơn cấp độ khuyến nghị .
Bạn thuộc lòng toàn bộ nhiệm vụ cùng các số và của chúng (và cả hai số , , vì bạn đã chơi trò này rất nhiều). Bạn cũng đủ giỏi để hoàn thành mọi nhiệm vụ, bất kể cấp độ khuyến nghị của nó và cấp độ của bạn. Bạn bắt đầu với XP. Bạn muốn hoàn thành tất cả các nhiệm vụ, mỗi nhiệm vụ đúng một lần, theo một thứ tự giúp bạn kiếm được nhiều XP nhất có thể.
Ví dụ, với ví dụ thứ nhất, số XP lớn nhất bạn có thể kiếm được là , theo cách sau. Đầu tiên hoàn thành nhiệm vụ thứ hai (bạn nhận XP, vì bạn đang ở cấp và hoàn thành một nhiệm vụ có cấp độ khuyến nghị ). Sau đó hoàn thành nhiệm vụ thứ nhất (bạn nhận XP, vì bạn vẫn ở cấp , còn cấp độ khuyến nghị là ). Với XP, bạn đang ở cấp . Cuối cùng hoàn thành nhiệm vụ thứ ba (bạn nhận XP, không có hệ số nhân, vì bạn đã ở cấp ).
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và : là số nhiệm vụ trong trò chơi, là số XP cần để lên mỗi cấp, và là hệ số nhân XP khi hoàn thành một nhiệm vụ trước khi đạt cấp độ khuyến nghị của nó.
Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và mô tả một nhiệm vụ: là số XP bạn nhận được khi hoàn thành nhiệm vụ đó lúc đang ở cấp độ bằng hoặc cao hơn cấp độ khuyến nghị, và là cấp độ khuyến nghị của nhiệm vụ.
Dữ liệu ra
In ra số XP lớn nhất có thể kiếm được sau khi hoàn thành tất cả các nhiệm vụ.
Ràng buộc
- .
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 10 2 15 1 2 2 9 1 |
43 | Thứ tự 2, 1, 3 như mô tả trong đề: . |
| 2 6 2 2 2 24 1 |
52 | Làm nhiệm vụ 1 trước: cấp nên nhận XP (vẫn cấp ). Sau đó làm nhiệm vụ 2: cấp nên nhận XP, tổng . Nếu làm nhiệm vụ 2 (cấp khuyến nghị nhỏ hơn) trước thì nhận XP, lên cấp , rồi nhiệm vụ 1 chỉ cho XP, tổng . |
Bình luận