Một băng chuyền có một số lượng ống chứa có dung tích khác nhau, mỗi ống đều đã được đổ đầy với sữa. Sữa từ băng chuyền này cần được chuyển vào ~m~ các thùng chứa. Có ràng buộc như sau:

• Khi sữa từ một ống được đổ vào một thùng, phải đổ hết toàn bộ sữa trong ống đó vào thùng đó. Nghĩa là không thể đổ sữa từ cùng một ống vào các thùng khác nhau.
• Sữa từ ống chứa phải được rót vào thùng theo thứ tự mà chúng xuất hiện trên băng chuyền. Nói cách khác, không thể chọn ngẫu nhiên một ống từ băng chuyền và rót vào thùng chứa.
• Thùng thứ ~i~ chỉ có thể được đổ đầy bằng sữa từ các ống xuất hiện trước các ống đổ sữa vào thùng thứ ~j~, với ~i < j~.

Cho số lượng các thùng ~m~, bạn cần đổ sữa từ tất cả các ống vào các thùng mà không để lại sữa trong bất kỳ ống nào. Các các thùng không nhất thiết phải có cùng dung tích. Nhiệm vụ của bạn là tìm dung tích nhỏ nhất có thể của thùng có dung tích lớn nhất.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \leq n \leq 1000)~, số lượng ống chứa trên băng chuyền và ~m~ ~(1 \leq m \leq 10^6)~, số lượng các thùng mà bạn phải chuyển sữa vào.
• Dòng tiếp theo chứa dung tích ~c~ ~(1 \leq c \leq 10^6)~ của mỗi ống chứa theo thứ tự xuất hiện trên băng chuyền. Lưu ý rằng, sữa đã được đổ đầy trong các ống chứa. Vì vậy, dung tích của ống chứa bằng với lượng sữa trong đó.

Output

Đối với mỗi bài toán, in ra số thứ tự của bài toán và kết quả mong muốn. Xem ví dụ để biết định dạng chính xác.

Sample Test

Input

3 2
4 78 9

Output

82

Dino rất thích ăn chuối. Có ~N~ nải chuối trước mặt Dino, nải thứ ~i~ chứa ~A_i~ quả.

Mẹ của Dino muốn bạn ấy ăn chuối lành mạnh. Bà ấy sẽ tới văn phòng và sẽ quay trở lại trong ~H~ giờ. Dino muốn đảm bảo rằng có thể ăn hết đống chuối vào lúc đó. Giả sử Dino đang ăn với tốc độ ~K~ quả chuối mỗi giờ. Ở mỗi giờ, bạn ấy sẽ chọn một số nải không rỗng và ăn ~K~ quả chuối từ đó (nếu nó có ít nhất ~K~ quả, nếu không Dino sẽ ăn tất cả đống ấy và kết thúc tiếng đó).

Dino thích ăn từ từ, nhưng vẫn muốn ăn hết đống chuối ấy. Tức là Dino thích tối thiểu ~K~ sao cho bạn ấy có thể ăn hết chuối trong ~H~ giờ. Giúp Dino tìm giá trị của ~K~.

Input

• Dòng đầu tiên chứa ~T~ (~1 \leq T \leq 10~) – biểu thị số test.
• Dòng đầu tiên của mỗi test chứa hai số nguyên ~N~ và ~H~ (~1 \leq N \leq 10^5, N \leq H \leq 10^9~) - số nải chuối và số giờ mẹ đi vắng.
• Dòng tiếp theo chứa ~N~ số nguyên, số thứ ~i~ thể hiện ~A_i~ (~A_i \leq 10^9~).

Output

Ở mỗi test, in ra một số thể hiện số thao tác ít nhất cần thực hiện.

Sample Test

Input:

3
3 3
1 2 3
3 4
1 2 3
4 5
4 3 2 7

Output:

3
2
4

Dino là người đứng đầu ngành công nghiệp khai thác gỗ thương mại, mới đây đã mua ~N~ cây. Bạn được cho chiều cao ban đầu của cây thứ ~i~ là ~H_i~ và mỗi tháng tăng được ~R_i~ mét chiều cao. Để đơn giản, bạn có thể coi tất cả các cây đều có đường kính bằng nhau. Nó cho phép chúng ta chỉ quan tâm đến chiều cao của cây khi nói về số lượng gỗ.

Trong vương quốc của Dino, pháp luật không cho cắt một phần của cây, vì vậy phải chặt toàn bộ cây để lấy gỗ. Ngoài ra, pháp luật còn cấm cắt những cây có độ cao thấp hơn ~L~ mét.

Hôm nay Dino nhận được một đơn đặt hang ~W~ mét (của chiều cao) gỗ. Dino muốn vận chuyển càng nhanh càng tốt. Tính số tháng ít nhất anh ta phải đợi để có thể đáp ứng đơn hàng. Bạn có thể giả định rằng máy cắt rất hiệu quả và không mất nhiều thời gian để chặt cây.

Input

• Dòng đầu tiên chứa 3 số nguyên ~N~, ~W~ và ~L~ (~1 \leq N \leq 10^5, 1 \leq W, L \leq 10^{18}~) - số lượng cây, lượng gỗ (tính theo mét) cần phải đáp ứng và chiều cao tối thiểu của cây để chặt.
• ~N~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~H_i~ và ~R_i~ (~1 \leq H_i, R_i \leq 10^9~).

Output

In ra một số nguyên duy nhất là: số tháng ít nhất để Dino có thể đáp ứng đơn hàng.

Sample Test

Input

3 74 51
2 2
5 7
2 9

Output

7

Note

• Sau ~6~ tháng, chiều cao của mỗi cây là ~14, 47, 56~. Dino chỉ được chặt cây thứ ba. Nhưng đáng tiếc là nó không đủ đáp ứng ~74~ mét gỗ.
• Sau ~7~ tháng, chiều cao của mỗi cây là ~16, 54, 65~. Lúc này Dino được chặt cây thứ ~2~ và cây thứ ~3~.
• Cắt cả ~2~ cây sẽ cung cấp cho anh ta ~119~ mét gỗ, đủ để đáp ứng hóa đơn.

Appy thích bóng bay! Appy muốn bạn tặng cho cô ây những quả bóng bay trong ~N~ ngày liên tiếp (được đánh số từ ~1~ tới ~N~).

Gọi số lượng bóng bay mà Appy muốn vào ngày thứ ~i~ là ~A_i~. Vấn đề là bạn chỉ có ~M~ bóng bay. May mắn là, bạn có thể đưa kẹo thay vì bóng bay. Vào ngày thứ ~i~, Appy chấp nhận ~B_i~ viên kẹo cho một quả bóng bay bạn không tặng cô ấy.

Nói cách khác, nếu bạn đưa ~X_i~ quả bóng bay cho Appy vào ngày thứ ~i~, thì bạn phải đưa cho cô ấy ~C_i = max(0, A_i - X_i)*B_i~ viên kẹo.

Nhiệm vụ của bạn là tối thiểu hóa số kẹo lớn nhất cần đưa cho Appy trong một ngày - tìm giá trị nhỏ nhất có thể của ~max(C_1, C_2, C_3, ..., C_N)~.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~M~ (~1 \leq N \leq 10^5, 0 \leq M \leq 10^{18}~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~0 \leq A_i \leq 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên ~B_1, B_2, \dots, B_N~ (~0 \leq B_i \leq 10^9~).

Output

In ra một dòng chứa một số nguyên - giá trị nhỏ nhất của ~max(C_1, C_2, C_3, ..., C_N)~.

Sample Test

Input:

5 3
1 2 3 4 5
1 2 3 4 5

Output:

15

Dino là một đầu bếp và anh ấy vừa mở một nhà hàng.

Nhà hàng mở trong ~N~ quãng thời gian ~[L_1, R_1)~, ~[L_2, R_2)~, ~\dots~, ~[L_N, R_N)~. Không có hai quãng nào bị đè lên nhau - tức là, với mọi ~i, j~ sao cho ~i \neq j~ thì ~R_i < L_j~ hoặc ~R_j < L_i~.

~M~ người (được đánh số từ ~1~ tới ~M~) lên kế hoạch ăn ở nhà hàng; gọi thời gian người thứ ~i~ đến là ~P_i~. Nếu nhà hàng mở vào thời gian đó, người này không phải đợi, nhưng nếu nó đang đóng, người này phải chờ cho tới khi nó mở cửa. Chú ý rằng nếu người này đến vào đúng thời gian nhà hàng đóng cửa, thì sẽ phải chờ tới lần mở cửa tiếp theo.

Với mỗi người, tính thời gian họ phải chờ đợi (có thể là không cần đợi), hoặc xác định người đó sẽ phải đợi mãi mãi.

Input

• Dòng đầu tiên chứa một số nguyên ~T~ (~1 \leq T \leq 100~) - biểu thị số test case.
• Dòng đầu tiên của mỗi test chứa hai số nguyên ~N~ và ~M~ (~1 \leq N,M \leq 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i~ và ~R_i~. (~1 \leq L_i, R_i \leq 10^9~).
• ~M~ dòng tiếp theo. Với mỗi ~i~, dòng thứ ~i~ chứa một số nguyên ~P_i~ (~1 \leq q_i \leq 10^9~).

Output

• Với mỗi test, in ra ~N~ dòng. Dòng thứ ~i~ chứa một số nguyên - thời gian người thứ ~i~ phải chờ đợi hoặc in ra -1 nếu người ấy phải chờ mãi mãi.

Sample Test

Input:

1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1

Output:

0
0
2
-1
1

Có ~N~ minion đang tranh đấu trong cuộc bầu cử tổng thống của ACM (Association of Cute Minions). Bọn chúng đang đứng thành một hàng, mỗi minion có mức độ ảnh hưởng là ~S_i~.

Một minion có thể bỏ nhiều phiếu. Tìm số lượng phiếu mà minion thứ ~i~ nhận được. Một minion ~j~ (~i \neq j~) sẽ bầu cho minion ~i~, nếu mức độ ảnh hưởng của minion thứ ~j~ lớn hơn hoặc bằng tổng độ ảnh hưởng của tất cả các minion ở giữa chúng (không tính minion thứ ~i~ và thứ ~j~).

Nhiệm vụ của bạn là tìm xem với mỗi ~i~ thì số lượng phiếu mà minion thứ ~i~ nhận được là bao nhiêu.

Input

• Dòng đầu tiên chứa ~T~ (~1 \leq T \leq 10^5~) - biểu thị số test case.
• Dòng đầu tiên của mỗi test chứa một số nguyên ~N~ (~1 \leq N \leq 10^5~) - số lượng minion.
• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ thể hiện ~S_i~ (~1 \leq S_i \leq 10^9~).

Lưu ý rằng: Tổng của ~N~ trong tất cả các test không vượt quá ~10^6~.

Output

• Ở mỗi test, in ra ~N~ số nguyên trên một dòng, số thứ ~i~ là số phiếu mà minion thứ ~i~ nhận được.

Sample Test

Input:

2
4
4 3 2 1
5
1 2 2 3 1

Output:

1 2 3 2
2 3 2 3 1

Bạn có thể đã giúp Chef và ngăn Doof phá hủy các số chẵn. Nhưng điều đó chỉ làm Dr.Doof tức giận hơn. Tuy nhiên, để phục vụ kế hoạch tiếp theo của mình, hắn cần thêm thời gian. Vì vậy, Doof đã xây dựng ~N~ bức tường để ngăn Chef làm phiền hắn. Bạn cần giúp Chef bằng cách cho biết số lượng bức tường mà anh ấy cần phá hủy để đến được chỗ Dr.Doof.

Cụ thể, toàn bộ khu vực có thể được biểu diễn là góc phần tư đầu tiên với gốc tọa độ ở góc dưới bên trái. Dr.Doof được đặt tại gốc tọa độ (~0, 0~). Có ~N~ bức tường, trong đó bức tường thứ ~i~ là một đoạn thẳng nối các điểm (~a_i, 0~) và (~0, a_i~). Với mỗi vị trí ban đầu của Chef (~x_j, y_j~), hãy tìm số bức tường anh ấy cần phá hủy trước khi đến được chỗ Doof. Rõ ràng Chef không thể bắt đầu từ một điểm nằm trên bức tường. Vì vậy, nếu (~x_j, y_j~) nằm trên bất kỳ bức tường nào đã cho, hãy in ra -1 trên một dòng mới.

Input

• Dòng đầu tiên chứa ~T~, biểu thị số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test chứa một số nguyên ~N~, biểu thị số lượng bức tường mà Dr.Doof đã xây dựng.
• Dòng tiếp theo chứa ~N~ số nguyên phân biệt, cách nhau bởi dấu cách, mỗi số biểu thị ~a_i~.
• Dòng tiếp theo chứa một số nguyên ~Q~, biểu thị số lần Chef yêu cầu bạn giúp đỡ.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_j~ và ~y_j~, biểu thị tọa độ điểm bắt đầu của Chef.

Output

Với mỗi truy vấn, in ra số lượng bức tường Chef cần phá để đến được chỗ Dr.Doof trên một dòng riêng. Nếu Chef cố gắng bắt đầu từ một điểm nằm trên bất kỳ bức tường nào, hãy in ra -1.

Constraints

• ~1 \leq T \leq 2\times10^2~
• ~1 \leq N, Q \leq 2\times10^5~
• ~1 \leq a_i \leq 10^9~
• ~0 \leq x_j, y_j \leq 10^9~
• ~a_1 < a_2 < a_3 < \dots < a_N~
• Tổng của ~N~ và ~Q~ trong tất cả các bộ test cho một tệp test cụ thể không vượt quá ~2\times10^5~.

Sample Test

Input:

1
2
1 3
5
0 0
2 0
0 4
1 1
1 2

Output:

0
1
2
1
-1

Explaination:

• Test đầu tiên có thể được biểu diễn bởi đồ thị dưới đây:

• Nếu Chef bắt đầu từ (~0, 0~), anh ấy có thể đến chỗ Dr.Doof mà không cần phá hủy bất kỳ bức tường nào.
• Nếu Chef bắt đầu từ (~2, 0~), anh ấy phải phá hủy bức tường thứ nhất.
• Nếu Chef bắt đầu từ (~0, 4~), anh ấy phải phá hủy cả hai bức tường.
• Nếu Chef bắt đầu từ (~1, 1~), anh ấy phải phá hủy bức tường thứ nhất.
• Vì (~1, 2~) nằm trên bức tường thứ hai, nên đáp án cho truy vấn cuối cùng là -1.

Polycarpus rất yêu thích bánh hamburger. Anh đặc biệt thích những chiếc hamburger do chính tay mình làm. Polycarpus nghĩ rằng chỉ có ba nguyên liệu ngon để làm hamburger là bánh mì, xúc xích và phô mai. Anh ghi lại công thức cho món "Le Hamburger de Polycarpus" yêu thích của mình dưới dạng một chuỗi ký tự 'B' (bánh mì), 'S' (xúc xích) và 'C' (phô mai). Các nguyên liệu trong công thức được xếp từ dưới lên trên.

Ví dụ, công thức "BSCBS" thể hiện hamburger với các nguyên liệu xếp từ dưới lên trên là bánh mì, xúc xích, phô mai, bánh mì và xúc xích lần nữa.

Polycarpus có ~n_b~ miếng bánh mì, ~n_s~ miếng xúc xích và ~n_c~ miếng phô mai trong bếp. Ngoài ra, cửa hàng gần đó có đầy đủ cả ba nguyên liệu này, với giá là ~p_b~ ruble cho mỗi miếng bánh mì, ~p_s~ ruble cho mỗi miếng xúc xích và ~p_c~ ruble cho mỗi miếng phô mai.

Polycarpus có ~r~ ruble và sẵn sàng đi mua sắm. Hỏi anh ấy có thể làm tối đa bao nhiêu chiếc hamburger? Bạn có thể giả định rằng Polycarpus không thể bẻ nhỏ hoặc cắt lát bất kỳ miếng bánh mì, xúc xích hoặc phô mai nào. Ngoài ra, cửa hàng có số lượng không giới hạn của mỗi loại nguyên liệu.

Input

• Dòng đầu tiên của đầu vào chứa một chuỗi không rỗng mô tả công thức "Le Hamburger de Polycarpus". Độ dài của chuỗi không vượt quá ~100~, chuỗi chỉ chứa các chữ cái 'B' (chữ B viết hoa), 'S' (chữ S viết hoa) và 'C' (chữ C viết hoa).
• Dòng thứ hai chứa ba số nguyên ~n_b~, ~n_s~, ~n_c~ (~1 \leq n_b, n_s, n_c \leq 100~) - số lượng miếng bánh mì, xúc xích và phô mai trong bếp của Polycarpus.
• Dòng thứ ba chứa ba số nguyên ~p_b, p_s, p_c~ (~1 \leq p_b, p_s, p_c \leq 100~) - giá của mỗi miếng bánh mì, xúc xích và phô mai trong cửa hàng.
• Cuối cùng, dòng thứ tư chứa số nguyên ~r~ (~1 \leq r \leq 10^{12}~) - số lượng ruble mà Polycarpus có.

Lưu ý, đừng sử dụng định dạng %lld để đọc hoặc ghi các số nguyên 64-bit trong C++. Nên sử dụng các luồng cin, cout hoặc định dạng %I64d.

Output

• In ra số lượng hamburger tối đa mà Polycarpus có thể làm. Nếu anh ấy không thể làm được chiếc hamburger nào, in ra 0.

Sample Test

Polycarp phát hiện ra có ~n~ đoạn trên đường phố. Một đoạn có chỉ số ~i~ được mô tả bởi hai số nguyên ~l_i~ và ~r_i~ - tọa độ của điểm đầu và điểm cuối của đoạn, tương ứng. Polycarp nhận ra rằng anh không cần tất cả các đoạn đó, vì vậy anh muốn xóa một số đoạn.

Polycarp cho rằng một tập hợp ~k~ đoạn là tốt nếu trong tập hợp đó có một đoạn [~l_i, r_i~] (~1 \leq i \leq k~) sao cho nó cắt tất cả các đoạn còn lại trong tập hợp (giao nhau phải là một điểm hoặc một đoạn).

Ví dụ, một tập hợp gồm 3 đoạn [[~1, 4~], [~2, 3~], [~3, 6~]] là tốt, vì đoạn [~2, 3~] cắt tất cả các đoạn trong tập hợp. Còn tập hợp ~4~ đoạn [[~1, 2~], [~2, 3~], [~3, 5~], [~4, 5~]] lại không tốt.

Polycarp tự hỏi, số lượng tối thiểu các đoạn anh phải xóa để các đoạn còn lại tạo thành một tập hợp tốt là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên ~t~ (~1 \leq t \leq 2\times10^5~) - số lượng các bài toán con. Sau đó là ~t~ bài toán con.
• Dòng đầu tiên của mỗi bài toán con chứa một số nguyên ~n~ (~1 \leq n \leq 2\times10^5~) - số lượng các đoạn. Tiếp theo là ~n~ dòng mô tả các đoạn.
• Mỗi đoạn được mô tả bởi hai số nguyên ~l~ và ~r~ (~1 \leq l \leq r \leq 10^9~) - tọa độ của điểm bắt đầu và điểm kết thúc của đoạn, tương ứng.
• Đảm bảo rằng tổng ~n~ của tất cả các bài toán con không vượt quá ~2\times10^5~.

Output

Với mỗi bài toán con, in ra một số nguyên duy nhất - số lượng tối thiểu các đoạn cần phải xóa để tập hợp các đoạn còn lại trở thành một tập hợp tốt.

Sample Test

Input:

4
3
1 4
2 3
3 6
4
1 2
2 3
3 5
4 5
5
1 2
3 8
4 5
6 7
9 10
5
1 5
2 4
3 5
3 8
4 8

Output:

0
1
2
0

Trong khi Vasya vừa ăn xong miếng pizza của mình, bài học đã bắt đầu. Vì đến muộn, thầy giáo đã đề nghị Vasya giải một bài toán thú vị. Vasya có một mảng ~a~ và một số nguyên ~x~. Nhiệm vụ của cậu là tìm số lượng cặp chỉ số (~i, j~) sao cho ~a_i \leq a_j~ và có đúng ~k~ số nguyên ~y~ thỏa mãn ~a_i \leq y \leq a_j~ và ~y~ chia hết cho ~x~.

Trong bài toán này, cặp (~i, j~) được coi là giống nhau với (~j, i~) chỉ khi ~i~ bằng ~j~. Ví dụ, cặp (~1, 2~) không phải là giống nhau với (~2, 1~).

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n~, ~x~, ~k~ (~1 \leq n \leq 10^5, 1 \leq x \leq 10^9, 0 \leq k \leq 10^9~) - trong đó ~n~ là kích thước của mảng ~a~, ~x~ và ~k~ là các số từ đề bài.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~1 \leq a_i \leq 10^9~) - các phần tử của mảng ~a~.

Output

• In ra số nguyên duy nhất là kết quả để bài.

Sample Test

Bạn được cung cấp một hoán vị ~p~ có độ dài ~n~ (một hoán vị có độ dài ~n~ là một mảng có độ dài ~n~, trong đó mỗi số nguyên từ ~1~ đến ~n~ xuất hiện chính xác một lần).

Bạn có thể thực hiện thao tác sau đây bất kỳ số lần nào (có thể là ~0~ lần):

• Chọn hai phần tử khác nhau ~x~ và ~y~ và xóa chúng khỏi hoán vị.
• Chèn giá trị nhỏ hơn trong hai số ~x~ và ~y~ vào đầu hoán vị.
• Chèn giá trị lớn hơn trong hai số ~x~ và ~y~ vào cuối hoán vị.

Ví dụ, nếu ~p~ = [~1, 5, 4, 2, 3~] và bạn muốn thực hiện thao tác với hai phần tử ~3~ và ~5~, sau bước đầu tiên, hoán vị trở thành ~p~ = [~1, 4, 2~]. Sau khi chèn các phần tử, hoán vị sẽ trở thành ~p~ = [~3, 1, 4, 2, 5~].

Nhiệm vụ của bạn là tính số lượng thao tác tối thiểu cần thực hiện để sắp xếp hoán vị ~p~ theo thứ tự tăng dần (tức là biến ~p~ thành một mảng sao cho ~p_1 < p_2 < ... < p_n~).

Input

• Dòng đầu tiên chứa một số nguyên ~t~ (~1 \leq t \leq 10^4~) - số lượng testcase.
• Với mỗi testcase, dòng đầu tiên chứa một số nguyên ~n~ (~1 \leq n \leq 200000~) - số lượng phần tử trong hoán vị.
• Dòng thứ hai chứa ~n~ số nguyên khác nhau từ ~1~ đến ~n~ - hoán vị ~p~ được cho.

Đảm bảo Tổng giá trị ~n~ của tất cả các bộ kiểm tra không vượt quá 200000.

Output

• Với mỗi bộ kiểm tra, in ra một số nguyên duy nhất - số lượng thao tác tối thiểu cần thực hiện để sắp xếp mảng ~p~ theo thứ tự tăng dần.

Sample Test

Input:

4
5
1 5 4 2 3
3
1 2 3
4
2 1 4 3
6
5 2 4 1 6 3

Output:

2
0
1
3

Note

Trong ví dụ đầu tiên, bạn có thể thực hiện như sau:

• Với hoán vị ~p~ = [~1, 5, 4, 2, 3~], chọn hai phần tử ~4~ và ~2~. Sau khi áp dụng thao tác, hoán vị trở thành ~p~ = [~2, 1, 5, 3, 4~].
• Với hoán vị ~p~ = [~2, 1, 5, 3, 4~], chọn hai phần tử ~1~ và ~5~. Sau khi áp dụng thao tác, hoán vị trở thành ~p~ = [~1, 2, 3, 4, 5~].

Khi Tôm có thời gian rảnh, cậu ta thường đến thư viện để đọc sách. Hôm nay, Tôm có ~t~ (phút) rảnh rỗi để đọc sách. Vì vậy, cậu ta đã mượn ~n~ cuốn sách từ thư viện và ước lượng thời gian cần để đọc mỗi cuốn sách. Gọi các cuốn sách được đánh số từ ~1~ đến ~n~, Tôm cần ~a_i~ phút để đọc cuốn sách thứ ~i~.

Tôm quyết định chọn một cuốn sách bất kỳ có số thứ tự ~i~ và bắt đầu đọc sách lần lượt từ cuốn này. Nói cách khác, anh sẽ đọc cuốn sách thứ ~i~, sau đó là cuốn thứ ~i+1~, rồi cuốn thứ ~i+2~, và tiếp tục như vậy. Quá trình này sẽ dừng lại khi Tôm hoặc hết thời gian rảnh hoặc đọc xong cuốn sách thứ ~n~. Tôm đọc từng cuốn sách đến hết, nghĩa là anh sẽ không bắt đầu đọc một cuốn sách nếu không đủ thời gian để đọc xong cuốn đó.

Hãy in ra số lượng sách tối đa mà Tôm có thể đọc.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~t~ (~1 \leq n \leq 10^5; 1 \leq t \leq 10^9~) - số lượng sách và số phút rảnh rỗi của Tôm.
• Dòng thứ hai chứa dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^4~) - trong đó ~a_i~ là số phút cần để đọc cuốn sách thứ ~i~.

Output

• In ra một số nguyên duy nhất - số lượng sách tối đa mà Tôm có thể đọc.

Sample Test