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
2014-08-11 15:48:27 Nắng
thêm bớt bựa bựa cuối cùng cụng qua test cuối :))
2013-12-31 10:36:09  
Duyệt phân tập + cận hợp lí => AC
2013-11-18 03:53:30 dương dễ thương vl
người gửi tên Khánh tự sướng v*i =))
2013-11-12 11:28:09 Code Phát TLE luôn
Lam thế nào để được 100 nhỉ :< cho cách làm tối ưu đi ác pan
2013-08-13 17:19:35 Dumbledore
Test này khiến ct mình sai, vậy mà vẫn AC
3 53
36 86
48 75
81 12
2013-04-13 09:08:19 [KC]★★★★ - darkmagician
QHD sao dc co 57,14 d nhi

2013-04-01 14:39:08 Khủng Long Lùn
71.42 huhuhu :((
2013-03-09 03:19:53 Try oh!
Ps coi dùm em xem sai test nào đc không ạ.
8857345. Thank nhiều ạ
2013-01-26 11:18:11 Chuyên Triết Tổng Hợp
85.71 =="
2013-01-17 12:30:42 CTKB LHP
giống bài toán kinh điển cái túi xách mà @@ sao ko đặt tên bài là knap cho dể tìm nhỉ @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.