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.|

DTTUI1 - Cái túi 1

Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có N cục vàng. Anh ấy muốn chuyển hết cả N cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.

Input

  • Dòng 1: Chứa 2 số nguyên: số cục vàng N (1 ≤ N ≤ 40) và tải trọng tối đa của túi M (1 ≤ M ≤ 109).
  • N dòng sau: Mỗi dòng chứa 2 số nguyên: trọng lượng Wi và giá trị Vi của cục vàng thứ i (1 ≤ Wi, Vi ≤ 108).

Output

  • Một số nguyên duy nhất là giá trị lớn nhất thu được.

Example

Input:
3 4
1 4
2 5
3 6

Output:
10

Được gửi lên bởi:khanhptnk
Ngày:2009-12-31
Thời gian chạy:0.200s-0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE

hide comments
2019-06-19 04:55:37
cho e hoi
bai no ghi bien dich gap loi la sao a
2018-12-24 10:19:37
1 dam 71,43 :((

Last edit: 2018-12-24 10:20:05
2018-07-12 06:42:52
EZ nhe lien he huuduc PBC nhe
2018-04-07 02:29:59
trau AC
2018-01-04 03:05:16
Khánh là kẻ tham lam, không muốn giúp ^^
2017-12-25 03:31:45
Compare quên để long long .-.
frostpixel aka.How 2 AC
2017-09-28 05:23:51
kham khảo
https://vietcodes.github.io/code/86/
2017-08-23 02:52:59
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1034/dttui1-spoj/


2017-07-27 14:18:09
Code AC: http://shink.in/F1HtO
2017-04-03 14:07:44
phân tập AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.