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

Giới hạn
  • Thời gian: 0.1s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 20000 bytes

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 .