Để tăng thêm tinh thần đoàn kết cho các bạn nhân viên, tập đoàn Viettel đã tổ chức một buổi hội trại cho toàn bộ nhân viên trong công ty. Như thường lệ, một hoạt động không thể thiếu của buổi hội trại là trò chơi "Nối vòng tay lớn". Bạn được phân công làm người quản trò cho trò chơi năm nay. Bạn đã đề ra luật chơi của trò chơi năm nay như sau.

~n~ bạn tham gia hội trại còn lại sẽ xếp thành một vòng tròn, các bạn được đánh số từ ~1~ đến ~n~ theo ngược chiều kim đồng hồ. Bạn thứ ~i+1~ sẽ đứng bên phải bạn thứ ~i~, và bạn thứ ~1~ sẽ đứng bên phải bạn thứ ~n~. Ở giữa vòng tròn là một đống sỏi với số lượng viên sỏi rất lớn, luôn đủ để phục vụ cho trò chơi.

Ban đầu, người quản trò sẽ phát cho mỗi bạn một phiếu, phiếu của bạn thứ ~i~ có chứa số ~a_i~ và con số này sẽ quyết định hành động của bạn thứ ~i~ khi đến lượt mình. Sau đó, người quản trò sẽ lấy ~p~ viên sỏi từ đống sỏi trung tâm và chuyền đống sỏi này cho bạn thứ ~1~. Khi đống sỏi được chuyền đến tay của bạn thứ ~i~ thì bạn cần thực hiện hành động sau:

• Nếu ~a_i < 0~ thì bạn cần lấy ra ~min(s, -a_i)~ viên sỏi từ đống sỏi trên tay để cho vào đống sỏi trung tâm (với ~s~ là số viên sỏi hiện tại trong đống sỏi)

• Nếu ~a_i > 0~ thì bạn cần cho thêm ~a_i~ viên sỏi từ đống sỏi trung tâm vào đống sỏi trên tay

• Nếu ~a_i = 0~ thì bạn sẽ không làm gì cả

Sau khi thực hiện hành động trên, nếu đống sỏi còn lại không quá ~q~ viên sỏi thì trò chơi sẽ kết thúc. Ngược lại, bạn cần chuyền đống sỏi trên tay đến cho bạn đứng bên phải mình, và trò chơi được tiếp tục.

Bạn cần tính xem rằng sau bao nhiêu lượt thì trò chơi sẽ kết thúc, hoặc cho biết rằng trò chơi sẽ không bao giờ kết thúc (để từ đó bạn có thể cân nhắc lại luật chơi mà mình đề ra).

Input

Dòng đầu tiên gồm ba số nguyên ~n~, ~p~, ~q~ (~1 \le n, p, q \le 10^5~, ~p > q~) — số bạn tham gia trò chơi, số viên sỏi được đưa cho bạn thứ ~1~ và điều kiện về số viên sỏi kết thúc trò chơi.

Dòng thứ hai gồm dãy số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^5 \le a_i \le 10^5~) — quy định hành động của từng bạn khi đến lượt của mình.

Output

In ra một số nguyên duy nhất là số lượt chơi mà trò chơi sẽ diễn ra, hoặc ~-1~ trong trường hợp trò chơi không bao giờ kết thúc.

Sample Input 1

3 8 3
1 -2 -3

Sample Output 1

5

Sample Input 2

4 9 6
-2 1 -2 3

Sample Output 2

3

Sample Input 3

4 9 5
-2 1 -2 3

Sample Output 3

-1

Sample Input 4

2 100000 1
-1 -1

Sample Output 4

99999

Sample Input 5

2 100 1
-200 100

Sample Output 5

1

Notes

Ở ví dụ thứ nhất, trò chơi sẽ diễn ra trong ~5~ lượt như sau:

• Ban đầu, người quản trò sẽ đưa cho bạn thứ nhất đống sỏi gồm ~p = 8~ viên sỏi (hành động này không tính là một lượt chơi).

• Với ~a_1 = 1~, bạn thứ nhất sẽ cho thêm ~1~ viên sỏi vào đống sỏi trên tay, và đưa đống sỏi đang có ~9~ viên cho bạn thứ hai.

• Với ~a_2 = -2~, bạn thứ hai sẽ lấy ra ~2~ viên sỏi khỏi đống sỏi trên tay, và đưa đống sỏi đang có ~7~ viên cho bạn thứ ba.

• Với ~a_3 = -3~, bạn thứ ba sẽ lấy ra ~3~ viên sỏi khỏi đống sỏi trên tay, và đưa đống sỏi đang có ~4~ viên cho bạn thứ nhất.

• Với ~a_1 = 1~, bạn thứ nhất sẽ cho thêm ~1~ viên sỏi vào đống sỏi trên tay, và đưa đống sỏi đang có ~5~ viên cho bạn thứ hai.

• Với ~a_2 = -2~, bạn thứ hai sẽ lấy ra ~2~ viên sỏi khỏi đống sỏi trên tay. Số viên sỏi lúc này là ~3~, tức là không quá ~q~ viên sỏi nên trò chơi sẽ dừng lại.

Ở ví dụ thứ hai, trò chơi sẽ diễn ra trong ~3~ lượt, và số viên sỏi của đống sỏi trên tay qua từng lượt chơi sẽ thay đổi như sau: ~9 \rightarrow 7 \rightarrow 8 \rightarrow 6~.

Ở ví dụ thứ ba, số viên sỏi của đống sỏi trên tay qua từng lượt chơi như sau: ~9 \rightarrow 7 \rightarrow 8 \rightarrow 6 \rightarrow 9 \rightarrow 7 \rightarrow 8 \rightarrow 6 \rightarrow 9 \rightarrow \ldots~ Có thể thấy rằng trò chơi sẽ không bao giờ kết thúc.

Ở ví dụ thứ năm, bạn thứ nhất sẽ lấy ra toàn bộ ~100~ viên sỏi khỏi đống sỏi trên tay. Đống sỏi không còn lại viên nào, do đó trò chơi kết thúc ngay tại lượt chơi đầu tiên.