Năm học này trường đại học A sẽ căn cứ vào điểm trung bình (ĐTB) để xét tuyển. ĐTB là điểm của các thí sinh đạt được sau khi tham dự kì thi đánh giá năng lực của nhà trường. Nhằm đảm bảo kết quả xét tuyển công bằng, khách quan và chọn được những thí sinh có đủ năng lực học tập, ban tuyển sinh nhà trường tổ chức kì thi đánh giá năng lực để chọn các thí sinh có ĐTB từ cao đến thấp cho đến khi đủ số lượng thí sinh cần tuyền. Do qui mô và tính chất của kì thi rất quan trọng nên các bạn thí sinh rất lo lắng. Để đậu vào trường thí sinh nào cũng phải cố gắng làm bài để có được ĐTB cao nhất.

Kỳ thi có ~N~ thí sinh tham dự, đề thi có ~M~ câu hỏi. Khi làm hồ sơ đăng kí dự thi, thí sinh thứ ~i~ có ĐTB là ~ai~. Trong đề thi câu hỏi thứ ~j~ có điểm là ~bj~. Yêu cầu mà đề thi đặt ra là để làm được câu hỏi thứ ~j~ bắt buộc thí sinh phải có ĐTB trước đó không nhỏ hơn ~b_j~ và sau khi làm xong câu hỏi thứ ~j~ thì điểm của câu hỏi thứ ~j~ sẽ được cộng vào ĐTB. (Giả sử những câu hỏi trong đề mà thí sinh đáp ứng được yêu cầu của đề sẽ làm đúng.)

Yêu cầu: Cho biết ĐTB ban đầu của ~N~ thí sinh và điểm của ~M~ câu hỏi. Em hãy lập trình giúp các thí sinh tìm phương án làm bài sao cho để khi thi xong ĐTB của mỗi thí sinh là cao nhất có thể.

Lưu ý: Nếu thí sinh không đủ điều kiện để thực được tất cả ~M~ câu hỏi trong đề thi, thì điểm xét tuyển là ĐTB mà ban đầu thí sinh có được khi đăng kí làm hồ sơ dự thi.

Dữ liệu

• Dòng đầu tiên chứa ~2~ số nguyên ~n~, ~m~ ~(1\le n, m \le 10^5)~, cho biết số lượng thí sinh tham dự kì thi và số lượng câu hỏi trong đề thi
• Dòng thứ hai chứa ~n~ số nguyên ~a1, a2, …, an~ ~(1≤ ai ≤ 10^9)~, cho biết ĐTB ban đầu khi đăng ký dự thi của ~N~ thí sinh
• Dòng thứ ba chứa ~m~ số nguyên dương ~b1, b2, …, bm~ ~(1\le bj\le 10^9 )~ cho biết điểm của câu hỏi thứ nhất đến câu hỏi thứ ~m~

Kết quả

Gồm ~n~ số nguyên nằm trên một dòng, số thứ ~i~ là ĐTB cao nhất của thí sinh thứ ~i~ sau kỳ thi.

Ví dụ

Input

5 4
4 6 1 2 9
7 31 2 15

Output

6 30 1 4 64

Ràng buộc

• Subtask ~1~: ~30\%~ điểm với test có ~1 \le n,m \le 10^3~, ~(1\le ai , bj \le 10^4)~
• Subtask ~2~: ~70\%~ điểm với test có ~n,m \le 10^5~, ~(1 \le ai , bj \le 10^9)~

Bòm vừa tốt nghiệp xuất sắc ngành CNTT tại một trường đại học danh tiếng. Bòm đã tìm hiểu, lên kế hoạch khởi nghiệp từ thời đang là sinh viên và nay là thời điểm mà anh ấy thực hiện kế hoạch đó. Qua tìm hiểu, Bòm biết được ~n~ công ty tiềm năng và có liên quan đến công việc của mình nên sẽ kết hợp với ~n~ công ty này. Các công ty được đánh số thứ tự ~1, 2, 3,…, n~. Điều kiện để hợp tác với công ty thứ ~i~ ~( i=1, 2, 3, \dots, n)~ là: Anh ấy đã hợp tác được với ít nhất ~ai~ công ty khác (trong ~n-1~ công ty còn lại) hoặc là mua một món quà có giá trị ~bi~ (đồng) để tặng cho công ty thứ ~i~.

Ban đầu, Bòm chưa hợp tác được với công ty nào. Hãy tính chi phí ít nhất để Bòm có thể hợp tác được với ~n~ công ty.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng công ty.
• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~ai~, ~bi~ ~(1 \leq i \leq n,~ ~0 \leq ai \leq n,~ ~0 \leq bi \leq 10^4)~.

Kết quả:

Một số nguyên duy nhất là chi phí thấp nhất để Bòm có thể hợp tác với tất cả ~n~ công ty.

Ví dụ

KHOINGHIEP.INP

4
3 6
1 2
0 5
3 7

KHOINGHIEP.OUT

6

Giải thích

Có ~n =4~ công ty , gọi ~e~ là số công ty mà Bòm đã hợp tác được , ban đều ~e=0~.

• Đầu tiên Bòm hợp tác với công ty ~3~ ~(a_3 = 0)~ suy ra ~e = 1~.
• Sau đó hợp tác với công ty ~2~ ~(a_2 = 1)~ suy ra ~e = 2~.
• Mua món quà trị giá ~6~ đồng để hợp tác với công ty ~1~ suy ra ~e = 3~.
• Cuối cùng sẽ hợp tác với công ty ~4~ ~(a_4 = 3)~. Vậy anh ấy mất tổng chi phí là ~6~ đồng để hợp tác với ~4~ công ty.

Ràng buộc

Công ty XYZ đang sở hữu ~n~ mỏ quặng, mỏ quặng thứ ~i~ ~(1 \leq i \leq n)~ có trữ lượng là ~A_i~. Công ty vừa ký hợp đồng cung cấp lượng quặng là ~S~. Để có lượng quặng khai thác đủ cho hợp đồng, Ban giám đốc quyết định đưa ra phương án ở các mỏ như sau:

• Lựa chọn ra một giới hạn ~k~ và chỉ khai thác ở mỏ có trữ lượng lớn hơn ~k~.

• Các mỏ có trữ lương lớn hơn ~k~ sẽ được khai thác cho đến khi trữ lượng đúng bằng ~k~.

• Lượng quặng khai thác thừa sẽ được lưu vào kho để phục vụ cho đơn hàng tiếp theo.

Yêu cầu

Hãy giúp Ban giám đốc xác định ~k~ để khai thác đủ đảm bảo hợp đồng, và lượng quặng khai thác thừa là ít nhất.

Dữ liệu

Vào từ file MINING.INP gồm:

• Dòng 1: Hai số nguyên dương ~n~, ~S~ ~(1 \leq n \leq 10^6)~.

• Dòng 2: Ghi ~n~ số nguyên dương ~A1, A2 , \dots An~ ~(1 \leq Ai \leq 10^9, i =1 \dots n) ~.

Dữ liệu đảm bảo ~S \leq A1+A2 +… +A_n~.

Kết quả

Ghi vào file MINING.OUT số nguyên ~k~ tìm được đảm bảo đủ lượng quặng cho hợp đồng và lượng quặng khai thác thừa là ít nhất.

Ví dụ 1

INPUT

4 3
5 3 7 8

OUTPUT

6

Ví dụ 2

INPUT

4 10
5 3 7 8

OUTPUT

3

Giải thích

Trong ví dụ ~1~, sẽ khai thác mỏ ~3~ và ~4~ với tổng là ~(7-6)+(8-6) = 3~, vửa đủ quặng cần thiết.

Trong ví dụ ~2~, sẽ khai thác mỏ ~1~, ~3~ và ~4~ với tổng là ~(5-3)+(7-3)+(8-3)=11~, lượng quặng thừa ~1~.

Không có phương án tối ưu hơn.

Ràng buộc

Sau khi xem các clip quảng cáo của Tân Hoa Banfood chuyên giới thiệu về các đặc sản Tây Bắc như: Nụ tam thất, rượu sâu chít, Cơm lam, mật ong rừng, ~\dots~ Sau kì nghỉ hè ở xứ này Thầy Sơn quyết định mua tặng cho gia dình mình mỗi người một ống cơm lam, có tất cả ~S~ người sẽ được nhận.

Được biết hiện cơm lam đang bán ở ~L~ cửa hàng và tại những cửa hàng này đang thực hiện giảm giá cho những người mua nhiều. Cửa hàng thứ i còn tất cả ~Fi~ ống cơm lam, bán với giá ~Pi~ đồng cho mỗi ống cơm lam, tuy nhiên nếu bạn mua ít nhất ~Ri~ ống thì bạn được hưởng giá ưu đãi – chỉ phải trả ~Qi~ đồng cho mỗi ống cơm lam, cửa hàng ~i~ Thầy Sơn chưa biết mua thế nào để mỗi người trong ~S~ bạn sẽ nhận được một ống cơm lam với tổng tiền phải trả là ít nhất. Bạn là lập trình viên Tin học, hãy tư vấn cho Thầy cách mua theo yêu cầu đặt ra. Bạn nên lưu ý Có thể mua nhiều hơn ~S~ ống cơm lam

Dữ liệu

• Dòng thứ nhất ghi hai số ~S~ và ~L~ ~(1\le S \le 100,~ ~0 \le L \le 100)~
• Mỗi dòng trong ~L~ dòng tiếp theo ghi thông tin về cửa hàng thứ ~i~ gồm ~4~ số ~Fi~, ~Pi~, ~Ri~, ~Qi~ ~(1\le Qi \le Pi \le 1000,~ ~1 \le Ri \le 100,~ ~0 \le Fi \le 100)~.

Kết quả

Một số nguyên duy nhất là số tiền cần thiết nhỏ nhất để mua cơm lam. Nếu cơm lam ở các cửa hàng không đủ để mua thì ghi giá trị ~-1~.

Ví dụ 1

Input

14 2
7 10 6 9
7 10 6 8

Output

119

Ví dụ 2

Input

15 2
10 15 2 1
10 13 6 2

Output

21

Ràng buộc

Nhân dịp lễ hội dừa tổ chức tại tỉnh Bến Tre. Ở Cồn Ốc xã Hưng Phong huyện Giồng Trôm có loại dừa rất nổi tiếng nên các đoàn tham quan cùng nhau đến thăm vườn dừa của gia đình ông Tám. Vườn dừa nhà ông được trồng ở khu đất ven sông hàm luông được phù sa bồi đắp quanh năm nên nước dừa có vị ngọt thanh cùng với hương vị của lá dứa. Chất lượng dừa không nơi nào có được

Tại thời điểm tham quan vườn dừa do chưa tới lứa bẻ (hái) dừa nên nhà Ông Tám hiện còn ~N~ quả dừa, trong các đoàn đến tham quan có ~M~ người muốn mua dừa, do mọi người muốn nhường nhau nên mỗi người chỉ được phép mua một quả, người thứ ~i~ cho biết sẵn sàng trả ~p_i~ (đồng) cho một quả dừa.

Vì sự hiếu khách và không muốn làm mất lòng khách tham quan nên ông Tám quyết định đưa ra một mức giá cố định là ~P~ (đồng) cho tất cả những người muốn mua, những người trả giá ~p_i \ge P~ sẽ mua được dừa với mức giá ~P~ (với điều kiện ông còn dừa).

Tuy hiếu khách nhưng vì miếng cơm manh áo nên ông Tám vẫn muốn thu được số tiền nhiều nhất có thế. Bạn hãy giúp ông đưa ra mức giá ~P~ để ông có thể thu được nhiều tiền nhất có thể, nếu có nhiều mức giá thỏa mãn thì hãy đưa ra một mức giá rẻ nhất.

Dữ liệu vào:

Nhập từ tệp văn bản DUABENTRE.INP có cấu trúc như sau:

• Dòng đầu chứa hai số nguyên dương ~N~ và ~M~ cách nhau bởi một dấu cách.
• Dòng sau ghi ~M~ số nguyên ~p1, p2, \dots , p_M~. Mỗi số cách nhau bởi một dấu cách.

Dữ liệu ra:

Ghi ra tệp văn bản DUABENTRE.OUT Một dòng duy nhất chứa hai số nguyên ~P~ là mức giá và ~S~ là tổng số tiền ông Tám thu được.

Ví dụ:

DUABENTRE.INP

3 5 
1 2 1 2 1

DUABENTRE.OUT

2 4

Giải thích:

• Test ~1~: Với mức giá ~2~ đồng, ông Tám sẽ bán được ~2~ quả dừa và thu về ~4~ đồng.

• Test ~2~: Với mức giá ~4~ đồng thì ông Tám bán được ~2~ quả dừa và thu về ~8~ đồng, với mức giá ~2~ đồng thì ông Tám bán được ~4~ quả dừa và thu về ~8~ đồng. Mức giá ~2~ đồng là mức giá rẻ hơn.

Ràng buộc :

Kì thi tin học trẻ toàn quốc tổ chức tại Quảng Bình, học sinh được tham gia rất nhiều trò chơi thú vị. Minh Thức là người đầu tiên tham gia vào trò chơi Chữ ~X~ may mắn.

Trò chơi gồm một bảng gồm ~N~ hàng và ~N~ cột, các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. Ô giao giữa hàng ~i~ và cột ~j~ gọi là ô ~(i, j)~ có ghi một giá trị nguyên ~a_{ij}~

Mỗi người chơi nhận được một chữ ~X~ có kích thước như nhau, chữ ~X~ gồm 2 nét có kích thước mỗi nét bằng ~K~ độ dài đường chéo các ô vuông đơn vị của bảng số (~K~ là một số nguyên dương lẻ). Người chơi sẽ đặt chữ ~X~ vào bảng số thỏa mãn các điều kiện sau:

• Hai nét của chữ ~X~ phải song song hoặc trùng với các đường chéo của bảng số.
• Chữ ~X~ phải nằm trọn vẹn trong bảng số.
• Giao điểm của hai nét chữ ~X~ phải là tâm của một ô vuông đơn vị của bảng số.

Điểm số nhận được của nhận được của người chơi bằng tổng số các giá trị của các ô mà chữ ~X~ đi qua. Với lợi thế là người đi đầu tiên Thức sẽ nắn nót để nhận được số điểm lớn nhất.

Yêu cầu

Hãy cho biết Thức có thể đạt điểm số lớn nhất bằng bao nhiêu?

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(N \le 1000,~ ~K~ lẻ, ~K \le N)~.
• ~N~ dòng sau mỗi dòng chứa ~N~ số nguyên là giá trị của các ô vuông đơn vị của bảng số đã cho, mỗi số cách nhau một khoảng trống và có giá trị tuyệt đối không lớn hơn ~10^9~.

Kết quả

Một số nguyên duy nhất là điểm số lớn nhất mà Thức có thể nhận được.

Ví dụ

Input

4 3 
5 -2 -30 -20
10 6 4 1
-7 5 4 2
20 2 -3 2

Output

36

Ràng buộc

Cho bảng số nguyên không âm kích thước ~𝑚~ x ~ 𝑛~ và hai số lẻ ~𝑟~, ~𝑐~. Hãy tìm bảng con kích thước ~𝑟 \times c~ để giá trị trung vị của các số trong bảng là nhỏ nhất.

Input

• Dòng đầu chứa bốn số nguyên ~𝑚, 𝑛, 𝑟, 𝑐~;
• Tiếp theo là ~𝑚~ dòng, mỗi dòng chứa ~𝑛~ số nguyên không âm mô tả bảng số (các số không vượt quá ~10^9~)

Output

• Gồm một số là trung vị nhỏ nhất tìm được.

Ví dụ

Input

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Output

9

Giải thích

Ràng buộc

• Subtask ~1~: ~m, n~ không vượt quá ~30~
• Subtask ~2~: ~m, n~ không vượt quá ~100~
• Subtask ~3~: ~m, n~ không vượt quá ~300~
• Subtask ~4~: ~m, n~ không vượt quá ~10^3~

Bờm được phân công làm thành viên của ban sao in đề thi tốt nghiệp THPT. Là một kì thi cấp quốc gia có tính chất rất quan trọng, trước khi tiến hành sao in đề thi anh ấy phải mở được các file đề thi của các môn thi, vì lý do bảo mật tất cả các file đề thi khi mở yêu cầu phải nhập vào đúng mật khẩu. Mật khẩu của mỗi đề thi do ban ra đề cung cấp theo một định dạng chung.

Bờm chỉ nhận được một file chứa các xâu kí tự, trong đó: xâu đầu tiên chứa dãy các kí tự, ~m~ xâu tiếp theo mỗi xâu chứa các kí tự phục vụ cho việc dò tìm mật khẩu (các kí tự trong file là kí tự thường từ a đến z). Vì đảm bảo tính tối mật của đề thi nên ban đề thi chỉ gửi file văn bản có cấu trúc như trên cho Bờm và hướng dẫn anh ấy cách tìm mật khẩu của mỗi đề thi như sau:

Mật khẩu của mỗi đề thi là một xâu kí tự được tạo ra có chiều dài ~L~, ~L~ là chiều dài, dài nhất đoạn đầu của xâu ~mi~ ~(i=1..M)~ xuất hiện Nếu không tìm thấy xâu ~mi~ xuất hiện trong xâu gốc thì ghi là #32.

Cùng là thành viên của ban sao in đề thi. Em hãy lập trình giúp Bờm tìm ra mật khẩu để mở đề của mỗi môn thi.

Dữ liệu

Cho từ file PASSWORD.INP chứa các xâu kí tự:

• Xâu ~S~ là xâu kí tự gốc ~(|S| \leq 10^6)~.
• ~M~ xâu tiếp theo ~m1, m2, \dots, m_m~ mỗi xâu kí tự phục vụ cho việc tìm ra mật khẩu các đề thi tương ứng cho ~M~ môn thi ~(M \leq 10)~.

Tổng độ dài các xâu ~mi~ không quá ~10^6~ ~(|m1| + |m2| + \dots |mn| \leq 10^6)~

Dữ liệu ra

Ghi vào file PASSWORD.OUT gồm ~M~ xâu: mỗi xâu chứa ~3~ thông tin ( mỗi thông tin cách nhau một khoảng trắng) nằm trên cùng một dòng:

• Xâu mật khẩu tìm được
• Vị trí ~V~ của xâu mật khẩu được tìm thấy trong xâu gốc
• Chiều dài ~L~ của xâu mật khẩu

Ví dụ

PASSWORD.INP

cabxabcdab
abcd
abxbher
mnpq
bcdpqmna
dabhfjhfjkghfjkhfjkhgkhgklhjglhjgjlkklh

PASSWORD.OUT

abcd 5 4
abx 2 3
#32
bcd 6 3
dab 8 3

Là đặc sản không thể thiếu được của người dân Nam bộ trong những ngày Tết cổ truyền của dân tộc. Với nguyên liệu là nếp, nước cốt dừa, đường, mè, hành,... Nhà Thầy Sơn là một trong những lò bánh được kể đến. Kinh nghiệm mỗi năm tết đến là đặc sản này làm không đủ bán. Do đó năm nay em của Thầy quyết định là sản xuất bánh để dự trữ trước những ngày giáp tết, chỉ có như vậy mới đủ bánh để phân phối. Nhưng có điều là bánh có thời hạn sử dụng rất ngắn không để lâu được do có chất dầu từ cốt dừa.

Trong nhà có ~n~ bao bánh. Mỗi ngày phải giao cho các đại lý là ~k~ bao, lúc nào trong nhà cũng dự trữ từ ~k~ bao bánh trở lên và nếu còn ít hơn thì sẽ giao hết các bao bánh. Nhưng vấn đề là ngày hết hạn sử dụng của bánh, những bao mà hết hạn sử dụng sẽ bị bỏ đi không dùng được. Do đó anh ấy sẽ chọn những bao bánh còn hạn sử dụng ít nhất sẽ giao trước. Cách này sẽ giúp anh ấy không những được lợi nhuận mà còn tránh việc phải bỏ đi các bao bánh vì quá hạn sử dụng. Hạn sử dụng trên mỗi bao bánh là một con số cho biết số ngày còn lại mà bánh còn sử dụng được.

Ví dụ: trên bao bánh ghi là ~1~ thì cho biết bao này phải được giao trong ngày hôm nay, số ~2~ là không thể để trể hơn ngày mai,...

Là học sinh giỏi về lập trình em hãy lập trình tính giúp em Thầy:

• Xác định ít nhất có bao nhiêu bao bánh quá hạn sử dụng phải bỏ đi vì không kịp giao ?
• Để các bao bánh không bị quá hạn sử dụng thì mỗi ngày anh ấy cần phải giao ít nhất bao nhiêu bao ?

Dữ liệu vào

Cho từ file banhphongsd.inp gồm hai dòng:

• Dòng thứ nhất ghi hai số nguyên dương ~n,~ ~k~ là số bao bánh có trong nhà và bao bánh phải giao mỗi ngày ~(1 ≤ n, k ≤ 10^6)~

• Dòng thứ hai ghi ~n~ số nguyên dương ~a1, a2, \dots, an~ trong đó ai là hạn sử dụng của bao bánh thứ ~i~ ~(0< ai ≤ 10^7, i = 1..n)~. Các số ghi trên cùng ~1~ dòng cách nhau một kí tự trắng.

Dữ liệu ra

Ghi vào file banhphongsd.out gồm hai dòng:

• Dòng thứ nhất ghi số bao bánh bị quá hạn sử dụng ít nhất nếu mỗi ngày anh ấy giao được ~k~ bao bánh.
• Dòng thứ hai ghi số bao bánh ít nhất mà mỗi ngày anh ấy cần phải giao được để không có bao nào quá hạn sử dụng.

Ví dụ

banhphongsd.inp

8 2
1 1 2 1 1 2 3 4

banhphongsd.out

2
4

Ràng buộc

Nhà xuất bản nhận được bản thảo một cuốn tiểu thuyết rất hay về đề tài khoa học viễn tưởng và nhận phát hành. Cuốn tiểu thuyết có ~n~ chương, chương thứ ~i~ có ~a_i~ trang, nếu in thành một cuốn sách thì quá dày, vì vậy người ta quyết định in thành ~k~ tập, mỗi chương phải nằm gọn trong một tập, tập ~1~ bao gồm một số chương đầu tiên, mỗi tập tiếp theo bao gồm một số chương tiếp, theo đúng trình tự như in tất cả các chương liên tiếp thành một cuốn. Ban biên tập phải có nhiệm vụ phân chia sao cho số trang của tập dày nhất là ít nhất.

Ví dụ, với ~n = 5~, số trang trong mỗi chương tương ứng lần lượt là ~3, 7, 12, 8, 5~ và dự kiến in thành ~3~ tập thì tập ~1~ sẽ chứa chương ~1~ và ~2~ với tổng số trang là ~10~, tập ~2~ chứa chương ~3~ với tổng số trang là ~12~, tập ~3~ chứa hai chương cuối với tổng số trang là ~13~. Như vậy, tập dày nhất có số trang là ~13~ và đây cũng là cách phân chia phù hợp với yêu cầu đã nêu.

Hãy xác định số trang của tập dày nhất nhận được sau kết quả làm việc của ban biên tập.

Dữ liệu

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \le k \le n \le10^5)~,
• Dòng thứ ~2~ chứa ~n~ số nguyên ~a1, a2, \dots, an~ ~(1 \le ai \le 10^9,~ ~i = 1 \rightarrow n)~.

Kết quả

Một số nguyên – số trang của tập dày nhất.

Ví dụ

Input

5 1
9 16 9 7750 6

Output

7790

Đường dẫn vào khách sạn nơi thường tổ chức những cuộc gặp gỡ của các tổ chức quốc tế được trang trí bằng một dãy ~n~ chậu hoa, mỗi loại hoa một màu được đánh số từ ~1~ đến ~n~ tương ứng với trình tự xuất hiện của màu trong bảng màu cầu vòng. Khi có hội nghị về một nước nào đó, các chậu hoa được bố trí theo trình tự thể hiện màu cờ của nước đó.

Hôm nay người ta chuẩn bị cho hội nghị khoa học về bảo vệ môi trường, Ban Tổ chức quyết định bố trí lại các chậu hoa phản ánh trạng thái cầu vồng, tức là phải sắp xếp các chậu hoa từ trái sang phải theo trình tự tăng dần của màu hoa (từ ~1~ đến ~n~). Hiện tại, ở vị trí ~i~ đang có chậu hoa màu ~c_i~, ~i = 1 \div n~, ~ci ≠ cj~ với ~i ≠ j~.

Ở thời đại cách mạng KHKT 4.0 mọi thứ đề được tự động hóa. Một robot được tách ra để bố trí lại các chậu hoa. Cứ mỗi đơn vị thời gian robot thực hiện được một thao tác đưa chậu hoa từ vị trí ~i~ về vị trí ~j~ với chi phí năng lượng là ~(i-j)^2~. Các thực hiện nhanh nhất là xét và đưa một số chậu về vị trí đúng của mình. Ví dụ, với trạng thái hiện tại ~1, 7, 3, 4, 5, 2, 6:~ Đưa chậu ~2~ về vị trí ~2~ với chi phí ~(6-2)^2~, có trạng thái ~1, 2, 7, 3, 4, 5, 6~, sau đó – đưa chậu ~7~ về vị trí cuối cùng với chi phí ~(7-3)^2~, kết quả là có dãy chậu hoa ~1, 2, 3, 4, 5, 6, 7~. Đây là cách thực hiện nhanh nhất về thời gian với chi phí năng lượng là ~4^2 + 4^2 = 32~. Đáng tiếc pin của robot chỉ còn e đơn vị năng lượng.

Hãy xác định khoảng thời gian ngắn nhất (tức là số thao tác ít nhất) robot hoàn thành nhiệm vụ được giao với phạm năng lượng hiện có..

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~e~ ~(1 \le n \le 10^5,~ ~1 \le e \le 10^{15})~,
• Dòng thứ hai chứa các số nguyên ~c1, c2, \dots, c_n~ – một hoán vị các số từ ~1~ đến ~n~.

Kết quả

Một số nguyên – số thao tác ít nhất xác định được. Nếu không có cách nào sắp xếp được trong phạm vi năng lượng ~e~ hiện có thì đưa ra một nguyên số ~-1~.

Ví dụ

Input

5 6
2 3 5 1 4

Output

3

Xưởng sản xuất bánh phồng nhà Thầy Sơn có ~N~ chi nhánh được xây dựng trên một con đường thẳng. Có thể mô tả con đường là một trục tọa độ, xưởng sản xuất nằm tại vị trí gốc tọa độ, ~N~ chi nhánh đặt tại các vị trí có tọa độ ~x1, x2, \dots, xN~ ~(0 < x1 < x2 < \dots < xN < 10^9)~, chi nhánh thứ ~i~ ~(i=1, 2, 3, \dots, N)~ có vị trí tại tọa độ ~xi~. Xưởng có ~M~ chiếc xe dùng để vận chuyển bánh phồng đến các chi nhánh. Chiếc xe thứ ~i~, chuyển bánh từ chi nhánh ~Si~ đến chi nhánh ~Fi~ ~(1 \le Si < Fi \le N)~, lượng nhiên liệu cần di chuyển cho ~1~ (đơn vị độ dài) là ~Ci~ (đơn vị thể tích) và số lần nạp nhiên liệu tối đa là ~Ri~, xe đi từ tọa độ ~x~ đên tọa độ ~y~ sẽ tiêu hao một lượng nhiên liệu là ~\lvert x - y \rvert \times Ci~. Các xe chỉ được di chuyển theo chiều dương của trục tọa độ và chỉ có thể nạp nhiên liệu khi đến vị trí của một chi nhánh nào đó. Xe không thể di chuyển nếu không còn nhiên liệu. Bình chứa nhiên liệu của ~M~ chiếc xe đều có dung tích giống nhau và bằng ~V~ (đơn vị thể tích). Khi bắt đầu xuất phát, nhiên liệu trên tất cả các xe đã đầy (không tính là một lần nạp nhiên liệu), mỗi lần nạp nhiên liệu, nhiên liệu sẽ được nạp đầy bình (tức là có ~V~ (đơn vị thể tích) nhiên liệu trong bình).

Yêu cầu

Hãy tính xem, giá trị ~V~ nhỏ nhất bằng bao nhiêu để với mọi chiếc xe đều có thể vận chuyển được bánh phồng, tức là chiếc xe thứ ~i~ có thể chuyển bánh phồng từ chi nhánh ~Si~ đến chi nhánh ~Fi~ với mọi ~i =1, 2, 3, \dots, M~.

Dữ liệu

• Dòng thứ nhất ghi ~2~ số nguyên dương ~N~ và ~M~ tương ứng là số chi nhánh và số xe chở bánh.
• Dòng thứ hai ghi ~N~ số nguyên dương ~x1, x2, \dots, xN~ ~(0 < x1 < x2 < \dots < xN < 10^9)~ tương ứng là tọa độ của ~N~ chi nhánh.
• ~M~ dòng cuối, dòng thứ ~i~ ~(i = 1,2,3,\dots, M)~ ghi ~4~ số nguyên ~Si,Fi,Ci,Ri~ ~(1 \le Si < Fi \le N; 1 \le Ci \le 10^9; 0 \le Ri \le N)~ là thông tin của xe thứ ~i~.

Kết quả

Một số nguyên là giá trị nhỏ nhất của ~V~ đề tất cả các xe đều có thể vận chuyển được bánh phồng.

Ví dụ

Input

5 2
1 3 8 12 15
1 3 10 0
2 4 5 1

Output

70

Giải thích

• Xe ~1~ chuyển hàng từ chi nhánh ~1~ đến chi nhánh ~3~ tức là từ tọa độ ~1~ đến tọa độ ~8~, xe không được nạp nhiên liệu lần nào do đó xe sử dụng nhiên liệu trong bình lúc xuất phát. Nên lượng nhiên liệu xe ~1~ cần ít nhất là ~\lvert 8 - 1 \rvert \times 10 = 70~. Vậy ~V=70~ thì xe ~1~ có thể chuyển hàng từ chi nhánh ~1~ đến chi nhánh ~3~.
• Xe ~2~ chuyển hàng từ chi nhánh ~2~ đến chi nhánh ~4~ tức là tọa độ ~3~ đến tọa độ ~12~. Xe được nạp nhiên liệu thêm ~1~ lần. Đi từ tọa độ 3 đến tọa độ 8 hết ~\lvert 8 - 3 \rvert \times 5 = 25~. Đi từ tọa độ ~8~ đến tọa độ ~12~ hết ~\lvert 12 - 8 \rvert \times 5 = 20~. Vậy ~V=25~ xe ~2~ đi từ chi nhánh ~2~ đến chi nhánh ~3~, nạp nhiên liệu tại chi nhánh ~3~ và di chuyển tiếp tới chi nhánh ~4~.
• Nên ~V~ nhỏ nhất để ~2~ xe có thể vận chuyển được bánh là ~70~.

Ràng buộc