Cho ~n~ đoạn sắt (1 ≤ ~n~ ≤ ~10^5~). Đoạn sắt thứ ~i~ có độ dài ~a_i~ (0 < ~a_i~ ≤ ~10^9~). Cần phải cắt các đoạn sắt đã cho thành các đoạn sao cho có được ~K~ đoạn sắt bằng nhau có độ dài nguyên. Có thể không cần cắt hết các đoạn sắt đã cho. Mỗi đoạn sắt bị cắt có thể có phần còn thừa khác 0.

Yêu cầu: Xác định độ dài lớn nhất của đoạn sắt có thể nhận được. Nếu không có cách cắt thì đưa ra số 0.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên ~N~, ~K~
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa số nguyên ~a_i~

Kết quả:

• Một dòng duy nhất ghi độ dài lớn nhất có thể nhận được.

Ví dụ

Input

4 11
802
743
547
539

Output

200

Mirko rất say mê với việc thiết kế máy tính cảm ứng, sau rất nhiều năm nghiên cứu Mirko đã thiết kế ra một loại máy tính thông minh rất hợp thời, tuy nhiên để sản phẩm đến được với người tiêu dùng với mức giá phải chăng và chất lượng tốt, Mirko quyết định sử dụng các thiết bị chính của nhà cung cấp có tiếng. Bốn bộ phận chính là: chip, màn hình cảm ứng, bo mạch và vỏ máy. Mỗi bộ phận có ~n~ nhà cung cấp, và mỗi bộ phận của một nhà cung cấp có một điểm đánh giá của các khách hàng (~v_i~) và có giá thành là ~c_i~. Tổng điểm đánh giá của chiếc máy tính bằng tổng điểm đánh giá của 4 bộ phận chính này. Bạn hãy giúp Mirko chọn ra được 4 nhà cung cấp cho 4 bộ phận chính của chiếc máy tính mà tổng điểm đánh giá là lớn nhất mà giá thành không quá ~V~.

Input:

• Dòng thứ nhất chứa ~n~ (2 ≤ ~n~ ≤103) là số nhà cung cấp thiết bị, và ~V~ (2 ≤ ~V~ ≤109) là giới hạn trên của tổng giá thành 4 bộ phận chính.
• Dòng thứ ~k~ tiếp theo (~k~ từ 1 đến 4) chứa ~n~ cặp số nguyên dương (~C_{k1}~, ~V_{k1}~) , (~C_{k2}~, ~V_{k2}~), … , (~C_{kn}~, ~V_{kn}~), (1 ≤ ~V_{ki}~,~C_{ki}~ ≤ 109).

Output: Một số duy nhất là tổng điểm đánh giá lớn nhất của máy tính mà tổng giá thành không quá ~V~ hoặc -1 nếu không tìm được.

Ví dụ

Input

2 10
2 2 3 3
2 2 4 5
2 2 5 8
2 2 6 8

Output

11

Giới hạn:

• 50 % số test có ~N~ <=100
• 50 % số test còn lại có ~N~ <= 1000

Vùng núi huyện Vĩnh Thạnh – tỉnh Bình Định có rất nhiều ngọn đồi núi bao trùm bởi rất nhiều cây gỗ lâu năm, cây cối quý hiếm ở đây rất nhiều nên cũng là địa điểm các lâm tặc khai thác gỗ lậu ngày càng tăng, để bảo vệ rừng ở nơi đây chi cục kiểm lâm tỉnh Bình Định muốn đặt người canh gác trên các ngọn đồi này.

Chi cục kiểm lâm tỉnh Bình Định không biết sẽ cần bao nhiêu người canh gác nếu như muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Chi cục kiểm lâm đã có bản đồ vùng núi huyện Vĩnh Thạnh là một ma trận gồm ~N~ (1 < ~N~ <= 700) hàng và ~M~ (1 < ~M~ <= 700) cột. Mỗi phần tử của ma trận là độ cao ~H_{ij}~ so với mặt nước biển (0 <= ~H_{ij}~ <= 10000) của ô (~i~, ~j~). Hãy giúp Chi cục kiểm lâm xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ ~X~ không quá 1 và chênh lệch tọa độ ~Y~ không quá 1.

Dữ liệu

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: ~N~ và ~M~
• Dòng 2..~N~ + 1: Dòng ~i~ + 1 mô tả hàng ~i~ của ma trận với ~M~ số nguyên cách nhau bởi dấu cách: ~H_{ij}~

Kết quả:

• Dòng 1: Một số nguyên duy nhất là số lượng đỉnh đồi.

Ví dụ

Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Output

3

Trong tiết học về dãy số tại trường, thầy giáo của Tý cho cả lớp chơi một trò chơi như sau:

Cho một dãy số ~A~ bao gồm ~N~ ~(N\leq 5*10^4)~ số nguyên, yêu cầu hãy chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các số ở phần bên phải. Với mỗi bước như vậy bạn được 1 điểm còn nếu không thể chia được thì trò chơi sẽ kết thúc. Sau khi chia thành công bạn sẽ được chọn dãy số bên trái hoặc bên phải để tiếp tục cuộc chơi với các bước như trên cho đến khi trò chơi kết thúc.

Là một học sinh giỏi trong lớp, Tý muốn đạt được số điểm cao nhất có thể. Bạn hãy tính xem số điểm lớn nhất mà Tý có thể đạt được là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên ghi một số nguyên ~T~ (1 ≤ ~T~ ≤ 10) là số lượng bộ dữ liệu. Mỗi bộ liệu bao gồm hai dòng:
• Dòng đầu tiên ghi một số nguyên ~N~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ phần tử của dãy ~A~ được ghi cách nhau bởi dấu cách (0 ≤ ~a_i~ ≤ ~10^9~).

Kết quả: Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.

Ví dụ

Input

3
3
3  3  3
4
2  2  2  2
7
4  1  0  1  1  0  1

Output

0
2
3

Tình hình kinh tế tại thành phố Quy Nhơn ngày càng phát triển. Sau một năm làm việc vất vả và chi tiêu hợp lí, nhiều người dân tại thành phố Quy Nhơn đã tích góp được một số tiền nhất định. Nắm bắt được thời cơ này, ngân hàng X đã tung ra rất nhiều chương trình khuyến mãi để thu hút người dân gửi tiết kiệm.

Giả sử có ~n~ khách hàng đang xếp hàng gửi tiền vào ngân hàng X. Số tiền mà mỗi khách hàng muốn gửi lần lượt là ~a_1~, ~a_2~,..., ~a_n~. Với mỗi khách hàng, nhân viên ngân hàng phải tốn thời gian là 1 phút để hoàn tất thủ tục hồ sơ. Vì cuối năm, các khách hàng rất bận và họ chỉ có thể chờ trong một khoảng thời gian nhất định mà thôi, sau khoảng thời gian đó họ sẽ đi và không gửi tiền ở ngân hàng X nữa. Thời gian mà các khách hàng có thể chờ lần lượt là ~t_1~, ~t_2~, ..., ~t_n~ (tính theo phút).

Giám đốc ngân hàng X muốn làm sao để có được nhiều tiền gửi vào ngân hàng mình nhất. Bạn hãy giúp ông ta đưa ra kế hoạch cho nhân viên lựa chọn thứ tự gửi tiền của các khách hàng sao cho số tiền ngân hàng có được là nhiều nhất (có thể phải chấp nhận từ chối một số khách hàng để đạt được mục đích). Cho:

Input:

• Dòng thứ nhất là số nguyên ~n~ (1 ≤ ~n~ ≤ 10000)
• Trong n dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~t_i~ (1 ≤ ~a_i~ ≤ ~10^5~, 0 ≤ ~t_i~ ≤ 1000).

Output:

• Là số nguyên xác định tổng số tiền nhiều nhất có thể thu được.

Ví dụ

Input

4
10 1
20 2
5 2
12 0

Output

42

Input

3
10 0
20 1
5 1

Output

30

Giới hạn:

• 60% số test có ~n~ ≤ 20, 0 ≤ ~t_i~ ≤ 100.
• 40% số test còn lại có ~n~ ≤ 10000 , 0 ≤ ~t_i~ ≤ 1000.

Năm 21XX, một cuộc khủng hoảng năng lượng nổ ra, quốc vương A quyết định cử một đội máy thăm dò lên sao Hỏa để tìm kiếm dầu mỏ. Đội thăm dò sẽ thăm dò trên một mảnh đất chia làm ~M*N~ ô bằng các máy thăm dò, mỗi máy thăm dò sẽ chiếm một ô vuông ~k*k~ và thăm dò trên diện tích mà nó chiếm, máy thăm dò có thể di chuyển sang các ô kề cạnh, khi thăm dò xong máy lập tức trở về (vì sợ hết nhiên liệu) chứ không nhảy sang các khu vực khác. Nhưng điều này là khó khó khăn đối với đội thăm dò.

Bạn hãy giúp họ đưa ra số máy thăm dò ít nhất sao cho tất cả các khu đất hình vuông ~k*k~ đều được thăm dò.

Input:

• Dòng đầu chứa 3 số ~M~, ~N~, ~K~ mỗi số cách nhau một dấu cách, 0 < ~M,N~ ≤ 1000; 0 < ~k~ < ~min(M,N)~;
• ~M~ dòng sau, mỗi dòng gồm ~N~ số, 0 biểu thị cho đất, 1 biểu thị cho đá không được đi qua.

Output: Gồm 1 số duy nhất ghi số lượng máy cần cử đi.

Ví dụ

Input

4 8 3
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0

Output

2

Giới hạn: Có ít nhất 60% số test ứng với ~M,N~<=100.