Sắp đến sinh nhật của thầy mrtee, các học sinh của tuyển Tin muốn mua tặng thầy một món quà. Sau khi tìm hiểu, họ đã biết được món quà thầy mrtee thích nhưng giá của món quà quá đắt nên lớp trưởng phải phát động một chương trình góp tiền mặt để mua quà tặng.

Tuyển Tin có ~n~ bạn đánh số từ ~1~ tới ~n~, số tiền nhiều nhất mà bạn thứ ~i~ có thể đóng góp là ~a_i~. Lớp trưởng muốn việc quyên góp tiền đạt được những yêu cầu sau:

• Số tiền mỗi người sẽ đóng góp là một số nguyên.
• Không có ai phải trả nhiều hơn khả năng của mình.
• Chênh lệch giữa người góp tiền ít nhất và nhiều nhất là nhỏ nhất có thể.
• Số tiền thu được đúng bằng số tiền để mua quà.

Biết tổng tiền cần có để mua quà và khả năng đóng góp của mỗi người, hãy xác định xem chênh lệch giữa người góp tiền ít nhất và nhiều nhất nhỏ nhất là bao nhiêu.

INPUT

Dòng đầu gồm 2 số nguyên dương ~n~, ~m~ (~n \le 10^5~, ~m \le 10^{18}~) với ~n~ là số người, ~m~ là số tiền cần trả để mua quà.

Dòng thứ hai gồm ~n~ số ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) lần lượt là số tiền nhiều nhất mà mỗi bạn có thể đóng góp.

OUTPUT

In ra kết quả của bài toán. Nếu không tìm được phương án theo yêu cầu thì in ra ~-1~

SAMPLE INPUT 1

4 20
10 10 4 4

SAMPLE OUTPUT 1

2

Giải thích: Cách quyên góp ~6, 6, 4, 4~

SAMPLE INPUT 2

3 7
1 1 4

SAMPLE OUTPUT 2

-1

Giải thích: Không có cách nào

SAMPLE INPUT 3

5 34
9 8 9 9 4

SAMPLE OUTPUT 3

4

Giải thích: Cách quyên góp ~8, 7, 8, 7, 4~

Cho ~2~ mảng ~a~ và ~b~ đều gồm ~n~ số nguyên dương và một số nguyên dương ~k~. Mảng số nguyên ~c~ gồm ~n^2~ phần tử được xây dựng bằng cách với mỗi cặp ~i,j~ thỏa mãn ~1 \le i,j \le n~, ta gán giá trị ~c_{(i-1)*n+j} = a_i + b_j~.

Sắp xếp mảng ~c~ lại theo thứ tự không giảm, hãy in ra số thứ ~k~ trong dãy ~c~ mới.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~.
• Dòng tiếp theo gồm ~n~ số nguyên dương mô tả dãy ~a~.
• Dòng cuối cùng gồm ~n~ số nguyên dương mô tả dãy ~b~.

Output

• In ra kết quả của bài toán.

Constraints

• ~1 \le n \le 10^5~, ~1 \le k \le n^2~.
• ~1 \le a_i,b_i \le 10^9~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

9

There are two ways to write error-free programs; only the third one works!

Cho hai số nguyên ~X~ và ~N~.

Hãy tìm số nguyên dương ~Y~ để ~X \times Y = N~

Input

• Dòng đầu tiên chứa số nguyên ~X~ ~(|X| \le 10^9, X \neq 0)~;
• Dòng thứ hai chứa số nguyên ~N~ ~(|N| \le 10^9)~.

Output

Nếu có số ~Y~ thoả mãn yêu cầu đề bài thì in ra ~Y~, ngược lại, in ra ~NA~.

Examples

Input

3
6

Output

2

Input

-3
6

Output

NA

Dino và Daisy đang học phép cộng. Bố bày cho hai bạn một trò chơi như sau:

• Ban đầu bố cho một dãy số gồm N phần tử: ~a_1, a_2, ..., a_N~;
• Daisy là em nên được bố ưu tiên, mỗi lượt chơi, Daisy sẽ chọn một số ~K~ ~(1 \le K \le 3)~. Sau đó Daisy sẽ lấy ~K~ số liên tiếp, rồi mới đến anh Dino lấy đúng ~K~ số liên tiếp khác (nếu cuối dãy không đủ ~K~ số thì Dino lấy nốt).

Yêu cầu: Hãy giúp Daisy chọn sao cho được tổng lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^5)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_i~ ~(a_i \le 10^6)~.

Output

In ra tổng lớn nhất mà Daisy chọn được.

Giới hạn

• Có 30% test tương ứng: ~N \le 10^2; a_i \le 10^3~;
• 30% test khác tương ứng: ~N \le 10^3; a_i \le 10^5~;
• 40% test còn lại không có ràng buộc gì thêm.

Sample Test 1

Input

4
5 4 3 2

Output

12

Giải thích: Daisy chọn ~3~ số đầu tiên, Dino chọn số cuối.

Sample Test 2

Input

6
10 8 7 11 15 20

Output

53

Giải thích:

• Daisy chọn ~2~ số đầu tiên: ~10, 8~;
• Dino có ~2~ số: ~7, 11~;
• Daisy chọn tiếp ~2~ số cuối: ~15, 20~.

Khôi có một dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một dãy con ~a_l, a_{l + 1}, \dots, a_{r}~ được gọi là pro nếu

• ~a_i + 1 = a_{i + 1},\ \forall l \le i \lt r~.

Ví dụ ~a = [1, 3, 4, 5, 2]~, thì dãy con ~[3, 4, 5]~ là dãy pro, dãy con ~[3]~ là dãy pro, nhưng dãy ~[3, 4, 5, 2]~ thì không. Chú ý dãy con có một phần tử cũng được gọi là pro.

Khôi định nghĩa độ pro của dãy ~a~ là dãy con dài nhất của ~a~ mà là dãy pro. Trong ví dụ trên, độ pro của dãy ~a = [1, 3, 4, 5, 2]~ là ~3~.

Để làm cho dãy số của mình trở nên pro nhất có thể, Khôi sẽ thực hiện tối đa ~k~ lần chỉnh sửa, mỗi lần chọn một vị trí ~i~, và tăng hoặc giảm ~a_i~ đi ~1~ đơn vị. Trong tất cả các cách chỉnh sửa có thể, Khôi muốn chọn ra cách có độ pro lớn nhất. Vì Khôi khá ga` nên hãy giúp Khôi tìm ra độ pro có thể này nhé!

Input (vào từ file văn bản proseq.inp)

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le n \le 5 \times 10^5,\ 0 \le k \le 10^{15})~.
• Dòng sau chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9)~.

Output (ghi ra file văn bản proseq.out)

• In ra một sô nguyên duy nhất là độ pro lớn nhất có thể sau khi thực hiện tối đa ~k~ lần chỉnh sửa.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~k = 0~.
• Subtask 2 (~20\%~ số điểm): ~n \le 500~.
• Subtask 3 (~30\%~ số điểm): ~n \le 5000~
• Subtask 4 (~30\%~ số điểm): Không có điều kiện gì thêm.

Sample Input 1

5 0
1 3 4 2 5

Sample Output 1

2

Notes: Ta không thể thực hiện bước chỉnh sửa nào, nên dãy ~a~ giữ nguyên và có độ pro là ~2~.

Sample Input 2

6 5
2 0 3 3 6 8

Sample Output 2

5

Notes: Ta có thể biến dãy ~a~ về ~[1, 2, 3, 4, 5, 8]~ và có độ pro là ~5~.