Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NTHUGE - Cái túi 3

Ngân hàng của LC có 1 hầm chứa đá quý lớn, là nơi nhòm ngó của biết bao tên trộm khét tiếng. Nhưng với sự bố trí bảo mật của LC, chưa một ai có thể chinh phục hầm đá quý này. Vì thế, nó được mang biệt danh "bất khả xâm phạm".

Một lần, Vua Trộm quyết định phải phá tan cái biệt danh kia. Với sự khéo léo của mình, hắn ta đã lọt được vào trong hầm. (Còn việc hắn đột nhập như thế nào thì phải hỏi hắn mới biết, hắn không chịu tiết lộ bí quyết nhà nghề =)) )Trước mắt hắn là N ngăn tủ, mỗi ngăn tủ chứa 1 viên đá quý với trọng lượng W và giá trị V. Vua trộm mang theo 1 chiếc túi lớn. Hắn ta chỉ chịu ra về khi tổng trọng lượng các viên đá quý đạt tối thiểu là L, tuy nhiên hắn lại không thể để chiếc túi nặng quá R vì lý do sức khoẻ :)) và hắn sợ bị hệ thống bảo mật tối tân của LC phát hiện.

Hãy giúp Vua Trộm chọn ra các viên đá quý để mang về sao cho tổng giá trị là lớn nhất.

Input

  • Dòng đầu tiên ghi 3 số N,L,R (N≤32; L,R≤1018)
  • N dòng tiếp theo mỗi dòng ghi 2 số W[i] và V[i] tương ứng với loại đá quý thứ i (W[i],V[i]≤1015)

Output

  • Một dòng duy nhất là kết quả tìm được

Example

Input:
3 6 8
3 10
7 3
8 2
Output:
3

Được gửi lên bởi:senga
Ngày:2010-02-22
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET

hide comments
2014-04-18 02:47:47 Hà Tiến Giang
t k giúp trộm đâu :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.