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

HUGEKNAP - Cái túi ( Hard version )

Cho N đồ vật , vật i có khối lượng W[i] và giá trị là V[i] . Một cái túi có thể chịu được khối lượng tối đa là M , quá thì sẽ rách. Hãy tìm cách nhét 1 số đồ vật vào trong túi sao cho túi không bị rách và tổng giá trị của các đồ vật nhét vào là lớn nhất.

Các tiêu chí yêu cầu : Chương trình của bạn chạy đúng , bộ nhớ thông báo ngoài status nhỏ hơn 850 KB ( với Free Pascal ) và nhỏ hơn 2850 KB ( với C++ ) thì bạn mới được coi là accept . Yêu cầu này đơn giản là vì bài này nguồn gốc là dành cho Turbo Pascal nên khi add lên trên này thì đành phải giới hạn với các bạn 1 chút .
Nâng time limit từ 3s lên 5s cho các bạn dễ làm hơn vậy.

Input

Dòng đầu tiên là số nguyên T là số bộ test . ( 1 ≤ T ≤ 40 )
Mỗi bộ test sẽ có format như sau :
Dòng 1 : 2 số nguyên dương N , M ( 1 ≤ N ≤ 10000 , 1 ≤ M ≤ 1000 ) .
Dòng 2 : Gồm N số nguyên là W[i] ( 1 ≤ W[i] ≤ 1000 ) .
Dòng 3 : Gồm N số nguyên là V[i] ( 1 ≤ V[i] ≤ 10000 ) .

Output

Với mỗi bộ test :
Dòng đầu tiên ghi ra giá trị lớn nhất có thể đạt được và số K là số đồ vật lựa chọn .
Dòng thứ 2 ghi ra chỉ số của K đồ vật được chọn .

Example

Input:
1
3 4
1 2 3
4 5 6

Output:
10 2
1 3

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-06
Thời gian chạy:0.100s
Giới hạn mã nguồn:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:CPP PAS-FPC
Nguồn bài:Folklore - Sách thầy Hoàng , mục bài tập tự giải , bài số 1 .

hide comments
2017-07-23 17:08:05
tao lậy mệt vl :((((((((
2017-07-23 16:11:29
100 bài nộp chưa 1 người ac :D
2015-09-08 14:19:09
https://thewizard6296.wordpress.com/2015/09/04/5/
2014-09-20 05:03:09 [CHV] Bác Thợ Sãn
sư cha tk Ngọc..Chỉ rình rình đọc cmt
2014-02-08 09:59:45 Nhung anh sao dem
Turbo Pascal memory limit = 64kb thì phải :)
2013-09-18 15:05:52 a;slkfjasl;fkj
nếu ra cho turbo pascal thì sao ạ?
2012-10-13 17:02:00 Stupider
nếu có nhiều cách lấy đc giá trị lớn nhất thì in là cách ngắn nhất à :-/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.