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 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 qobi SCM guile ST TCL TEXT WHITESPACE

hide comments
2012-09-05 08:02:03 ðẹp trai bẩm sinh
đệ qui 2^n được 75 rồi :P
2012-07-16 13:38:32 Nguyen Nhat Long
QHD + tham lam =66.67 @@
2012-07-16 13:31:12 Nguyen Nhat Long
QHD 58.33d @@
2012-07-09 15:06:26 Tumo@gmail.com
Duyệt
2012-06-08 00:52:50 Ðã Code Là Quyết Ac
m đâu phải là vấn đề chính căn bản là n thôi :)
2012-02-03 15:09:15 Noyethug
đệ quy + cận + chặn times..:D
2011-07-12 16:57:03 Confident
bai nay lam sao day moi nguoi lon qua
2011-06-20 00:58:35 ndduy1995
Bai nay du lieu lon qua xD
2011-04-20 13:31:48 SOAP MacTavish
Ma uj, bai nay ko QHD dk dau, thuat toan Tung noi chi AC dk bai CAR ma thoi :))
2011-01-20 12:56:44 Nguyễn Hứa Gia Thuyên
bai nay lam theo QHD = mang 2 chieu trong sach LMH day ma :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.