NTHUGE - Cái túi 3

• Thời gian: 0.2s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

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≤10 ¹⁸ )
• 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]≤10 ¹⁵ )

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

• Người up: iamtnl