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%)

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

MrTôm muốn Dino. Hiện tại, MrTôm đã đi làm và sẽ trở về sau ~H~ giờ. Dino muốn đảm bảo rằng anh ta có thể ăn hết xoài trước khi MrTôm trở về.

Giả sử Dino 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ờ đó).

Dino thích ăn chậm, nhưng vẫn muốn ăn hết xoài đúng giờ. Hãy giúp Dino 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 đó MrTôm 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~.

Constraints

• ~1 \leq N \leq 10^5~
• ~N \leq H \leq 10^9~
• ~1 \leq A_i \leq 10^9~

Sample Test

Input:

4 5
4 3 2 7

Output:

4

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ó ~N~ que có độ dài khác nhau và cần tạo một số tam giác từ các que này. Một tam giác hợp lệ nếu diện tích của nó lớn hơn ~0~. Nhiệm vụ của bạn là tìm số cách có thể tạo một tam giác hợp lệ bằng cách sử dụng các que.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ (~3 \leq N \leq 2000~) - số lượng que.
• Dòng tiếp theo chứa ~N~ số nguyên biểu thị độ dài của các que. Bạn có thể giả sử rằng các độ dài 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 có thể tạo ra một tam giác hợp lệ.

Sample Test

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