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

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

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

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

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~

Nông dân John đã xây một chuồng dài mới, với ~N~ (~2 \leq N \leq 10^5~) ô chuồng. Các ô chuồng được đặt dọc theo một đường thẳng tại các vị trí ~x_1, x_2, \dots, x_N~ (~0 \leq x_i \leq 10^9~).

Ông có ~C~ (~2 \leq C \leq N~) con bò, nhưng những con bò này không thích bố cục chuồng như vậy và trở nên hung hăng với nhau khi bị nhốt chung. Để ngăn bò làm hại lẫn nhau, John muốn sắp xếp các con bò vào các ô chuồng sao cho khoảng cách nhỏ nhất giữa bất kỳ hai con bò nào là lớn nhất có thể. Hãy tìm khoảng cách nhỏ nhất lớn nhất đó.

Input

• Dòng thứ nhất gồm hai số nguyên ~N~ và ~C~.
• ~N~ dòng sau, mỗi dòng gồm một số nguyên ~x_i~.

Output

• Một dòng duy nhất: in ra khoảng cách lớn nhất.

Sample test

Input:

5 3
1
2
8
4
9

Output:

3

Note

John có thể đặt ba con bò ở vị trí ~1, 4, 9~, dẫn đến khoảng cách nhỏ nhất giữa 2 con bò là ~3~

Bizon the Champion không chỉ quyến rũ mà còn rất thông minh.

Trong khi một số người trong chúng ta đang học bảng cửu chương, Bizon the Champion lại vui chơi theo cách của riêng mình. Bizon the Champion đã vẽ một bảng nhân ~n \times m~, trong đó phần tử ở giao điểm của hàng thứ ~i~ và cột thứ ~j~ bằng ~i \times j~ (các hàng và cột của bảng được đánh số bắt đầu từ ~1~). Sau đó, có người hỏi: số nào trong bảng là số lớn thứ ~k~? Bizon the Champion luôn trả lời chính xác và ngay lập tức. Bạn có thể lặp lại thành công của anh ấy không?

Xét bảng nhân đã cho. Nếu bạn viết ra tất cả ~n \times m~ số từ bảng theo thứ tự không giảm, thì số thứ ~k~ viết ra được gọi là số lớn thứ ~k~.

Input

• Dòng duy nhất chứa các số nguyên ~n~, ~m~ và ~k~ (~1 \leq n, m \leq 5\times10^5; 1 \leq k \leq n\times m~).

Output

• In ra số lớn thứ ~k~ trong bảng nhân ~n \times m~.

Sample Test

mrtee đi bộ vào buổi đêm trên một con đường thẳng độ dài ~l~, được soi sáng bởi ~n~ đèn lồng. Xét hệ tọa độ với đầu đường tương ứng với điểm ~0~, và cuối đường tương ứng với điểm ~l~. Khi đó đèn lồng thứ ~i~ ở điểm ~a_i~. Đèn lồng soi sáng tất cả các điểm trên đường có khoảng cách tới nó không vượt quá ~d~, với ~d~ là một số dương, giống nhau với tất cả đèn lồng.

mrtee thắc mắc: Bán kính ánh sáng ~d~ nhỏ nhất là bao nhiêu để các đèn lồng có thể soi sáng toàn bộ con đường?

Input

Dòng đầu tiên gồm hai số nguyên ~n, l~ (~1 \le n \le 1000, 1 \le l \le 10^9~) - số lượng đèn lồng và độ dài con đường.

Dòng tiếp theo gồm ~n~ số nguyên ~a_i~ (~0 \le a_i \le l~). Nhiều đèn lồng có thể được đặt tại cùng một điểm. Các đèn lồng có thể được đặt ở hai đầu đường.

Output

In ra bán kính ánh sáng nhỏ nhất ~d~ cần để soi sáng toàn bộ đường. Câu trả lời được coi là đúng nếu chênh lệch không vượt quá ~10^{-9}~.

Sample test:

Input 1:

7 15
15 5 3 7 9 14 0

Output 1:

2.5000000000

Input 2:

2 5
2 5

Output 2:

2.0000000000

Note

Xét ví dụ thứ hai. Với ~d = 2~ đèn lồng đầu tiên sẽ soi sáng đoạn ~[0, 4]~ của con đường, và đèn lồng thứ hai sẽ soi sáng đoạn ~[3, 5]~ . Do đó, cả con đường sẽ được soi sáng.

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

Cho dãy ~a~ gồm ~n~ phần tử và một số nguyên dương ~k~. Hãy tìm đoạn ~a[l..r]~ có độ dài tối thiểu là ~k~ sao cho ~med(l, r)~ đạt giá trị lớn nhất. Biết rằng: ~med(l, r)~ là phần tử trung vị sau khi sắp xếp đoạn ~a[l..r]~ theo thứ tự không giảm, phần tử trung vị của một dãy có độ dài ~n~ là phần tử ở vị trí thứ ~\lfloor \frac{n+1}{2} \rfloor~ của dãy đó.

Ví dụ: Với ~A = \{3, 1, 4, 1, 5, 1, 2, 1, 2\}~, ~med(1, 5) = 3; \ med(6, 9) = 1~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le k \le n \le 10^5)~;
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n; \ 1 \le i \le n)~.

Output

In ra một số nguyên là giá trị lớn nhất của ~med(l, r)~ thoả mãn đề bài.

Examples

Input

4 2
1 3 4 2

Output

3

Giải thích

Chọn ~l=2, r=4~. Khi đó, ~med(2, 4) = 3~.