Tại một nông trường chè ở Thái Nguyên, có N luống chè xếp thành một hàng ngang. Luống thứ i có sản lượng là A_i kg. Giám đốc cần phân công K công nhân đi thu hoạch. Để đảm bảo tính liên tục, mỗi công nhân phải thu hoạch một dải các luống chè liên tiếp nhau. Hãy tìm cách chia N luống chè này cho K công nhân sao cho khối lượng chè lớn nhất mà một công nhân phải hái là nhỏ nhất có thể.

Input:

Dòng 1: Hai số nguyên N và K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Output: Khối lượng chè lớn nhất mà một công nhân phải hái trong phương án tối ưu.

Ví dụ:

Input:

5 3
2 4 1 3 5

Output:

6

(Giải thích: Chia thành 3 đoạn: [2, 4], [1, 3], [5]. Tổng các đoạn lần lượt là 6, 4, 5. Khối lượng lớn nhất là 6).

Một chuỗi gen sinh học kỳ lạ chỉ được cấu thành từ 3 loại protein ký hiệu là A, B, và C. Các nhà nghiên cứu phát hiện ra rằng, một đoạn gen con sẽ mang tính đột biến nếu nó chứa ít nhất một protein A, ít nhất một protein B và ít nhất một protein C. Hãy đếm số lượng đoạn gen con liên tiếp mang tính đột biến trong chuỗi gen S cho trước.

Input: Một chuỗi S chỉ gồm các ký tự A, B, C (Độ dài <= 10^5).

Output: Số lượng đoạn con chứa ít nhất một A, một B và một C.

Ví dụ:

Input:

ABCBCA

Output:

7

Một cánh đồng năng lượng mặt trời là một bảng kích thước N x M, mỗi ô (i, j) ghi nhận mức sản lượng điện Cij. Tổng công ty sẽ liên tục gửi xuống Q yêu cầu truy vấn. Mỗi yêu cầu gồm 4 số r1, c1, r2, c2 đại diện cho tọa độ góc trên trái và góc dưới phải của một khu vực hình chữ nhật. Với mỗi truy vấn, hãy báo cáo tổng sản lượng điện trong khu vực đó.

Input:

Dòng 1: Ba số nguyên N, M, Q (1 <= N, M <= 1000, 1 <= Q <= 10^5).

N dòng tiếp: Mỗi dòng M số nguyên Cij (0 <= Cij <= 1000).

Q dòng tiếp: Mỗi dòng 4 số nguyên r1, c1, r2, c2 (1 <= r1 <= r2 <= N, 1 <= c1 <= c2 <= M).

Output: In ra Q dòng, mỗi dòng là kết quả của một truy vấn.

Ví dụ:

Input:

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

Output:

14
24

Một cỗ máy đổi tiền được nạp sẵn N loại mệnh giá tiền xu khác nhau (số lượng mỗi loại xu được coi là vô hạn). Khách hàng cần đổi một tờ tiền có giá trị S. Hãy lập trình cho cỗ máy tìm cách nhả ra đúng số tiền S bằng số lượng đồng xu ít nhất.

Input:

Dòng 1: Hai số nguyên N và S (1 <= N <= 100, 1 <= S <= 10^4).

Dòng 2: N số nguyên là các mệnh giá tiền xu.

Output: Số lượng đồng xu ít nhất cần dùng. Nếu không thể đổi được, in ra -1.

Ví dụ:

Input:

3 11
1 5 10

Output:

2

(Giải thích: Dùng 1 đồng mệnh giá 10 và 1 đồng mệnh giá 1).