HUGEKNAP - Cái túi ( Hard version )
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 20000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.
Chú ý:
- Bài này Time limit trên vn.spoj.com bị đặt quá nhỏ (lý do là khi máy chấm SPOJ cập nhật lên máy Cube đã tự động chỉnh time limit xuống 0.1s - quá nhỏ).
- Bài này ban đầu trên vn.spoj.com có ghi chú giới hạn bộ nhớ 850 KB ( với Free Pascal ) và 2850 KB ( với C++ ). Tuy nhiên với Time limit hiện tại thì mình nghĩ không thể làm được.
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
- Người up: hard7771988
- Nguồn bài: Folklore - Sách thầy Hoàng , mục bài tập tự giải , bài số 1 .