Sản xuất đồ chơi

Xưởng sản xuất đồ chơi XYZ đã mua các lô hàng ống đàn để làm nguyên liệu sản xuất đàn ống. Mỗi lô gồm $n$ ($n>2$) ống đàn với độ cao đôi một khác nhau lần lượt là $h_1,h_2,\dots ,h_n$ để khi nhạc công gõ vào các ống đàn với độ cao khác nhau, ống sẽ phát ra các âm thanh khác nhau. Ống đàn thứ $i$ có trọng lượng là $h_i\times m$ ($1\le i\le n$).

Quy trình sản xuất đàn của hãng thực hiện theo dây chuyền tự động hoàn toàn như sau: Bắt đầu, robot $A$ sẽ tự động mở một lô và xếp lần lượt $n$ ống có độ cao $h_1,h_2,\dots ,h_n$ lên dây chuyền. Tiếp theo, các ống sẽ được robot $B$ phân thành $s$ ($1<s\le n$) lô con. Lô con thứ nhất gồm các ống từ $1$ đến $k_1$, lô con thứ hai gồm các ống từ $k_1+1$ đến $k_2$, ..., lô con thứ $s$ gồm các ống từ $k_{s-1}+1$ đến $n$ ($1\le k_1<k_2<\dots <k_{s-1}<n$). Mỗi một lô con sẽ được chuyển cho robot $C$ để lắp thành một chiếc đàn. Robot $C$ sẽ tiến hành sắp xếp các ống thành một dãy đảm bảo điều kiện có không quá $w$ vị trí ống đứng trước cao hơn ống đứng liền kề sau nó (nếu có). Có thể có nhiều phương án sắp xếp các ống đàn trong một lô con thỏa mãn điều kiện này. Mỗi một phương án như vậy sẽ được gọi là một loại đàn.

Sau khi khảo sát thị hiếu người tiêu dùng, Ban giám đốc nhận thấy: trọng lượng hợp lý của một chiếc đàn (được tính bởi tổng trọng lượng của các ống đàn) là một số không nhỏ hơn $b_{min}$ và không lớn hơn $b_{max}$; ngoài ra, không có hai khách hàng nào lại muốn dùng đàn giống nhau. Dễ thấy, số lượng loại đàn khác nhau có thể tạo ra phụ thuộc vào việc phân $n$ ống thành $s$ lô con. Do đó, Ban giám đốc muốn lựa chọn cách phân $n$ ống thành $s$ lô con sao cho tổng trọng lượng các ống trong mỗi lô con đều nằm trong đoạn từ $b_{min}$ đến $b_{max}$ và số lượng các loại đàn ống khác nhau có thể sản xuất được là nhiều nhất.

Yêu cầu: Hãy tìm cách phân $n$ ống thành $s$ lô con thỏa mãn các điều kiện đặt ra và sao cho số lượng loại đàn ống khác nhau có thể sản xuất được là nhiều nhất.

Dữ liệu vào

• Dòng đầu tiên chứa $T$ ($T\le 10$) là số lượng bộ dữ liệu. Tiếp đến là $T$ nhóm dòng, mỗi nhóm dòng cho thông tin về một bộ dữ liệu theo khuôn dạng sau:
  • Dòng thứ nhất chứa sáu số nguyên dương $n$, $s$, $w$, $m$, $b_{min}$, $b_{max}$.
  • Dòng thứ hai gồm $n$ số nguyên dương $h_1,h_2,\dots ,h_n$ mô tả độ cao của $n$ ống.

Giới hạn: $m<100$; $b_{min},b_{max}<{10}^9$; $h_i<{10}^6$. Dữ liệu bảo đảm bài toán có lời giải.

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng chứa một số nguyên là số lượng các loại đàn khác nhau tìm được tương ứng với bộ dữ liệu vào.

Ràng buộc

• $1\le T\le 10$.
• $2<n\le 200$; $1<s\le n$; $1\le w\le {10}^9$.
• $1\le m<100$; $1\le b_{min}\le b_{max}<{10}^9$.
• $1\le h_i<{10}^6$, các $h_i$ đôi một khác nhau.
• Luôn tồn tại cách phân $n$ ống thành $s$ lô con thỏa mãn điều kiện về trọng lượng.

Subtasks

• Subtask 1 ($30\%$ số test): $n\le 10$.
• Subtask 2 ($30\%$ số test): $10<n\le 30$.
• Subtask 3 ($40\%$ số test): $30<n\le 200$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ