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:Nguyễn Xuân Khánh
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 CPP C++ 4.3.2 CPP14 C99 CLPS LISP clisp LISP sbcl 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
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
2016-10-03 19:45:34
cứ tưỏng dễ ăn mà lại phải cho cả trạng thái ==
2016-09-10 09:31:46 Nguyễn Thành Nhân
Ai dùng long long/ long long int mà bị 92.86 thì đổi sang g++ 5.1 nhé
2016-05-18 11:27:28 Sơn Tùng M-TP
Vì sao chuyển từ long long sang int lại AC nhỉ? Mình cũng vậy, nhưng chẳng hiểu vì sao.
2016-05-18 10:41:34
... chuyển hết long long thành int là AC vcl đéo hiểu chuyện gì đang xảy ra (lúc trc dc 92.86)
2016-03-04 02:41:29
92,86 xem lại giới hạn biến, 40*10^8 quá int với longint rồi mấy bác :D
2015-12-22 14:44:07 Lê Trần Hữu Ðắc
sao e chia đôi phân tập + binary search mà đc có 92.86 ò :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.