AnBuffet - Ăn buffet
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: phuleethanh

     Đến năm 2030 Quảng Trị lúc này là một đô thị phát triển sầm uất, các quán cơm bụi đều chuyển loại hình thành các quán ăn buffet hiện đại tầm cỡ 3 sao.

     Bin lúc này là một doanh nhân thành đạt với công ty mà anh lập ra. Nhân dịp hè gặp lại người bạn cùng hội là Nhin. Anh đưa bạn mình ăn buffet tại nhà hàng Ý HẰNG.

     Nhà hàng có N món ăn được sắp xếp thành một hàng cố định trên bàn ăn. Quy định ăn buffet của quán có một điều khá đặc biệt: Nếu khách hàng chọn được các món ăn có tổng trọng lượng tối thiểu là u và không quá v thì sẽ được đưa vào danh sách chọn thăm may mắn của quán. Ai là chủ nhân của lá thăm có tổng giá trị các món ăn lớn nhất thì sẽ nhận phiếu ăn buffet miễn phí trong 1 năm.

     Bin và Nhin rất muốn giành được may mắn đó. Tuy nhiên công việc khá là khó vì có nhiều món ăn. Bạn hãy lập trình tính giúp cho hai bạn ấy.

Input:

-  Dòng đầu tiên ghi 3 số nguyên dương N, U, V (N<=32; U,V<=10^18)

-  N dòng tiếp theo mỗi dòng ghi hai số w[i] và v[i] là trọng lượng và giá trị của món ăn thứ I (do khách hàng khá đông nên mỗi món chỉ còn duy nhất 1 cái).  (w[i], v[i]<=10^15)

Output:

-  Một dòng duy nhất là giá trị lớn nhất của các món ăn mà Bin và Nhin có thể chọn.

Ví dụ

  • input
    3 6 8
    3 10
    7 3
    8 2
    output
    3
Back to Top