trang chủ / đề bài / icpc24_mt_a

Tên trộm

Đề bài

Mô tả

Một tên trộm đột nhập vào một ngôi nhà có N món đồ. Món đồ thứ i có khối lượng wi và giá trị ci. Tên trộm có một chiếc túi chịu được khối lượng tối đa W. Nếu tổng khối lượng các món đồ trong túi vượt quá W, túi sẽ rách và tên trộm không mang được gì.

Sau khi xếp đồ vào túi, tên trộm nghĩ: "Mình xách túi bằng một tay, vậy tay còn lại có thể cầm thêm một món đồ nữa." Theo ý nghĩ đó, tên trộm dùng tay còn trống để cầm thêm một món đồ, với điều kiện khối lượng của nó không vượt quá H.

Hãy xác định tổng giá trị lớn nhất của các món đồ mà tên trộm có thể mang đi.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên dương N, W và H (1≤N≤100, 1≤W,H≤109).
  • Mỗi dòng trong N dòng tiếp theo chứa hai số nguyên dương wi và ci (1≤wi≤109, 1≤ci≤103).

Dữ liệu ra

In ra một dòng chứa tổng giá trị lớn nhất mà tên trộm có thể mang đi.

Ràng buộc

  • 1≤N≤100
  • 1≤W,H≤109
  • 1≤wi≤109, 1≤ci≤103

Ví dụ

Input Output Giải thích
3 10 2
2 5
1 9
4 6
20 Túi chứa được cả ba món đồ, tổng giá trị là 20.
3 2 4
2 5
1 9
4 6
15 Tên trộm cho món đồ thứ 2 vào túi và cầm món đồ thứ 3 trên tay.

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