Cho mảng số nguyên dương A=(a1, a2, …, an) và một số nguyên dương S. Viết chương trình cho biết độ dài của dãy con nhỏ nhất sao cho tổng của dãy con lớn hơn hoặc bằng S. Nếu không có dãy con thì trả về giá trị là 0. Dãy con của A kí hiệu là Aij = (ai, ai+1, ai+2,…, aj), n >= i, j >= 1. Độ dài của dãy con chính là số phần tử của dãy con đó.
Input
Bao gồm 2*N+1 dòng:
Dòng 1: Chứa số nguyên dương N (1<= N <= 10). N là số lượng test case.
2*N Dòng tiếp theo là các testcase. Mỗi testcase gồm 2 dòng:
Dòng thứ 1: là hai số nguyên S (1 <= S <= 109 ) và n (1 <= n <= 105).
Dòng thứ 2: là các số nguyên dương trong mảng A ( 1 <= ai <= 5 x 105). Các số nguyên cách nhau bởi dấu cách
Output
N dòng, mỗi dòng là độ dài của dãy con.
Ví dụ:
|
input |
output |
|
3 7 6 2 3 1 2 4 3 4 3 1 4 4 11 8 1 1 1 1 1 1 1 1 |
2 1 0 |
