Cho dãy ~a~ có ~m~ số nguyên ~a_1, a_2, \ldots, a_m~.

Dãy ~b~ có ~n~ số nguyên ~b_1, b_2, \ldots, b_n~. Hãy tìm số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Input

Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ ~(0 < m, n \leq 10^5)~.

Dòng tiếp theo chứa ~m~ số nguyên ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.

Dòng tiếp theo chứa ~n~ số nguyên ~b_i~ ~(-10^9 \leq b_i \leq 10^9)~.

Output

Số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Sample

Input

3 5
1 2 3
1 3 3 4 5

Output

2

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

• Dòng đầu gồm 2 số nguyên ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(|k| \le 10^6)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Cho một dãy số ~A~ nguyên không âm gồm ~n~ phần tử và một số ~k~ bất kì ~(k<=n)~. Ta định nghĩa ý nghĩa của dãy số này chính bằng trung bình cộng lớn nhất của một đoạn con liên tiếp bất kì trong dãy với độ dài lớn hơn hoặc bằng ~k~. Nói cách khác, ý nghĩa của dãy chính bằng ~max(f(l,r))~, với ~f(l,r)~ là trung bình cộng của đoạn con ~[l,r]~ và ~(1 \le l \le r \le n, r-l+1 \ge k)~. Hãy lập trình để đi tìm ý nghĩa của dãy.

Input:

• Dòng đầu gồm 3 số ~n,k,h~.
• Dòng sau là ~n~ phần tử của dãy ~A~. (~1 \le k \le n \le 10^5, 0 \le h \le 1~), (~A_i \le 10^5 ~ với mọi ~1 \le i \le n~).

Output:

Nếu ~h = 0~, in ra phần nguyên của kết quả tìm được. Ngược lại nếu ~h = 1~, in ra kết quả lấy 3 chữ số thập phân sau dấu phẩy.

Sample Test 1

Input:

4 2 0 
17 0 14 1

Output:

10

Sample Test 2

Input:

4 2 1
17 0 14 1

Output:

10.333

Giải thích:

• Ở test 1, đoạn con thỏa mãn là ~[1,3]~ có giá trị trung bình là 10.(333). Tuy nhiên do ~h = 0~ nên ta chỉ lấy phần nguyên của kết quả là 10.
• Ở test 2, tương tự test 1, nhưng do ~h = 1~ nên ta lấy kết quả = 10.333

Ràng buộc

• Subtask 1: ~n \le 1000~. (50%)
• Subtask 2: ~n \le 10^5, h = 0~. (30%)
• Subtask 3: ~n \le 10^5~. (20%)

(F. De. Jong luôn nhớ về thời chơi cho clb Ajax Amsterdam)

F. De. Jong rất thích ăn xoài. Trước mặt F. De. Jong có ~N~ đống xoài; mỗi đống thứ ~i~ chứa ~A_i~ quả xoài.

Huấn luyện viên của CLB Barcelona - Xavi muốn tài năng trẻ này ăn hết xoài. Hiện tại, Xavi đã đi làm và sẽ trở về sau ~H~ giờ. F. De. Jong muốn đảm bảo rằng anh ấy có thể ăn hết xoài trước khi Xavi trở về.

Giả sử F. De. Jong có tốc độ ăn là ~K~ quả xoài mỗi giờ. Mỗi giờ, anh sẽ chọn một đống xoài. Nếu đống đó chứa ít nhất ~K~ quả xoài, anh sẽ ăn ~K~ quả xoài từ đống đó. Ngược lại, anh sẽ ăn hết cả đống (và sẽ không ăn thêm quả xoài nào trong giờ đó).

F. De. Jong thích ăn chậm, nhưng vẫn muốn ăn hết xoài đúng giờ. Hãy giúp F. De. Jong tìm giá trị ~K~ nhỏ nhất để anh có thể ăn hết xoài trong ~H~ giờ.

Input

Dòng đầu tiên của chứa hai số nguyên ~N~ và ~H~, tương ứng là số đống xoài và số giờ sau đó Xavi sẽ trở về trụ sở.

Dòng thứ hai chứa ~N~ số nguyên được phân tách bằng khoảng trắng ~A_1, A_2, ..., A_N~ là số lượng quả xoài trong mỗi đống.

Output

In ra một dòng chứa một số nguyên duy nhất - giá trị nhỏ nhất có thể của ~K~.

Sample

Input

4 5
4 3 2 7

Output

4

Giới hạn

~1 \leq N \leq 10^5~

~N \leq H \leq 10^9~

~1 \leq A_i \leq 10^9~

Subtask

Có ~30\%~ số test có ~n<=100~

Có ~30\%~ số test khác có ~n<=1000~

Các test khác không có ràng buộc gì thêm

Appy thích bóng bay! Cô ấy muốn bạn 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 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 thay, bạn có thể cho cô ấy 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 cho Appy ~X_i~ quả bóng bay vào ngày thứ ~i~, thì bạn phải đưa cô ấy ~C_i = \max(0, A_i - X_i) \cdot 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~.

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~.

Dòng thứ ba chứa ~N~ số nguyên ~B_1, B_2, ..., B_N~.

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

Input

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

Output

15

Giới hạn:

~1 \leq N \leq 10^5~

~0 \leq M \leq 10^{18}~

~0 \leq A_i, B_i \leq 10^9~

Bạn được cho ~N~ que diêm có độ dài khác nhau; bạn phải tạo ra một số tam giác bằng cách sử dụng các que diêm này. Một tam giác được coi là hợp lệ nếu diện tích của nó là dương. Nhiệm vụ của bạn là tìm số cách bạn có thể tạo ra một tam giác hợp lệ bằng các que diêm.

Input

Một dòng chứa một số nguyên ~N~ (~3 \leq N \leq 2000~).

Dòng tiếp theo chứa ~N~ số nguyên thể hiện độ dài của các que diêm. Bạn có thể giả định rằng các độ dài này là khác nhau và mỗi độ dài nằm trong khoảng ~[1, 10^9]~.

Output

In ra tổng số cách mà một tam giác hợp lệ có thể được tạo ra.

Sample

Input

4
100 211 212 121

Output

4

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~ containers. Các ràng buộc như sau:

Khi sữa từ một ống được đổ vào một container, phải đổ hết sữa trong ống đó vào container đó. Tức là không thể đổ sữa từ cùng một ống vào các container khác nhau. Sữa từ ống phải được đổ vào container theo thứ tự xuất hiện của chúng trên băng chuyền. Tức là không thể chọn một ống Container thứ ~i~ phải được đổ sữa chỉ từ các ống xuất hiện trước các ống đổ sữa vào container thứ ~j~, với ~i < j~.

Cho số lượng containers ~m~, bạn cần đổ sữa từ tất cả các ống vào containers mà không để lại sữa trong bất kỳ ống nào. Các containers 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 container 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 containers 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

Input

3 2
4 78 9

Output

82