Dừng tại tổng đạt ngưỡng (First Prefix Reaching a Threshold)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ số nguyên không âm theo thứ tự nhập và ngưỡng dương $T$. Cộng lần lượt từ số thứ nhất. Hãy tìm vị trí nhỏ nhất $i$ sao cho $a_1+\cdots+a_i\ge T$ (đánh số từ 1). Nếu mọi tổng tiền tố đều nhỏ hơn $T$, in -1. Khi đạt ngưỡng có thể dừng bằng break; các phần tử phía sau không thể làm vị trí đầu tiên nhỏ hơn.

Input

Dòng đầu chứa $n$ và $T$; tiếp theo đúng $n$ số nguyên $a_i$, phân cách bằng khoảng trắng hoặc xuống dòng. $1\le n\le100000$, $1\le T\le10^{12}$, $0\le a_i\le10^9$.

Output

In vị trí đầu tiên có tổng tiền tố lớn hơn hoặc bằng $T$, hoặc -1.

Subtask

• Subtask 1 (20%): $1\le n\le 8$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

• Subtask 2 (30%): $1\le n\le 1000$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

• Subtask 3 (50%): $1\le n\le 100000$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

Ví dụ

Ví dụ 1

Input:

4 8
3 5 1 2

Output:

2

Giải thích:

T=8. Tổng tiền tố theo từng vị trí: 1→3, 2→8. Đạt ngưỡng lần đầu ở vị trí 2.

Ví dụ 2

Input:

3 20
3 5 1

Output:

-1

Giải thích:

T=20. Tổng tiền tố theo từng vị trí: 1→3, 2→8, 3→9. Không có tổng tiền tố nào đạt ngưỡng, nên in -1.