trang chủ / đề bài / icpcwf20_i

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 v 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 lớn nhất sao cho bạn có ít nhất L·v XP.

Mỗi nhiệm vụ có một số XP x và một cấp độ khuyến nghị d. Nếu bạn hoàn thành nhiệm vụ khi cấp độ của bạn ít nhất là d, bạn nhận được x XP. Còn nếu bạn hoàn thành nhiệm vụ khi cấp độ của bạn nhỏ hơn d, bạn nhận được c·x XP. Hằng số c 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ị d.

Bạn thuộc lòng toàn bộ n nhiệm vụ cùng các số x và d của chúng (và cả hai số v, c, 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 0 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à 43, theo cách sau. Đầu tiên hoàn thành nhiệm vụ thứ hai (bạn nhận 4 XP, vì bạn đang ở cấp 0 và hoàn thành một nhiệm vụ có cấp độ khuyến nghị 2). Sau đó hoàn thành nhiệm vụ thứ nhất (bạn nhận 30 XP, vì bạn vẫn ở cấp 0, còn cấp độ khuyến nghị là 1). Với 34 XP, bạn đang ở cấp 3. Cuối cùng hoàn thành nhiệm vụ thứ ba (bạn nhận 9 XP, không có hệ số nhân, vì bạn đã ở cấp 3).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên n, v và c: n là số nhiệm vụ trong trò chơi, v là số XP cần để lên mỗi cấp, và c 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à n dòng, mỗi dòng chứa hai số nguyên x và d mô tả một nhiệm vụ: x 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à d 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

  • 1≤n≤2000.
  • 1≤v≤2000.
  • 2≤c≤2000.
  • 1≤x≤2000.
  • 1≤d≤106.

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 đề: 4+30+9=43.
2 6 2
2 2
24 1
52 Làm nhiệm vụ 1 trước: cấp 0<2 nên nhận 4 XP (vẫn cấp 0). Sau đó làm nhiệm vụ 2: cấp 0<1 nên nhận 48 XP, tổng 52. Nếu làm nhiệm vụ 2 (cấp khuyến nghị nhỏ hơn) trước thì nhận 48 XP, lên cấp 8, rồi nhiệm vụ 1 chỉ cho 2 XP, tổng 50.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0