Bài tập

Trong một vương quốc nọ, có một mỏ khoáng sản quý hiếm trải dài theo một con suối. Mỏ được chia thành \(L\) khu vực, được đánh số từ \(1\) đến \(L\). Mỗi khu vực thứ \(i\) chứa một lượng khoáng sản có giá trị là \(C_i\). Vua của vương quốc muốn thuê \(G\) đội thợ mỏ để khai thác toàn bộ mỏ khoáng sản này.

Để việc khai thác được hiệu quả và công bằng, nhà vua quyết định chia con suối thành \(G\) đoạn liên tiếp, và mỗi đội thợ mỏ sẽ chịu trách nhiệm khai thác một đoạn. Chi phí cho việc khai thác một khu vực được tính bằng cách lấy giá trị khoáng sản của khu vực đó nhân với tổng số khu vực trong đoạn mà nó thuộc về. Tổng chi phí khai thác của cả mỏ sẽ là tổng chi phí của tất cả các khu vực.

Nhà vua muốn tìm cách phân chia mỏ khoáng sản thành \(G\) đoạn sao cho tổng chi phí khai thác là nhỏ nhất. Bạn, một vị quan cận thần tài ba, được giao nhiệm vụ tìm ra cách phân chia tối ưu này.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(L\) và \(G\) (\(1 \le L \le 8000\), $1 \le G \le min(800, L) $).
• \(L\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(C_i\) (\(1 \le C_i \le 10^9\)), là giá trị của dãy số.

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Example

6 3
11 11 11 24 26 100

299

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(1 \leq L \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(1 \leq L \leq 800\).
• Subtask \(3\) (\(40\%\) số điểm) : \(1 \leq L \leq 8000\).

Để nắm bắt được tình hình đọc sách tại thư viện A quản lí thư viện đã yêu cầu cô nhân viên thư viện thống kê số lượt người tham gia đọc sách tại thư viện và đếm số ngày nhiều nhất có cùng lượt người đọc.

Cô nhân viên thư viện ghi lại liệt kê \(n\) ngày đọc sách với số lượt người đọc của từng ngày cụ thể, em hãy giúp cô nhân viên thư viện phân việc còn lại là đưa ra tổng số lượt người đọc sách và số ngày có cùng lượt người đọc là nhiều nhất có thể.

Input

Dữ liệu vào: Đọc từ tệp TK.INP có cấu trúc:

• Dòng đầu ghi số nguyên dương \(n\) (\(n \le 10^5\)).
• Dòng thứ hai ghi \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5, i = 1, 2, 3, ..., n\)).

Output

Dữ liệu ra: Ghi vào tệp TK.OUT có cấu trúc:

• Dòng đầu ghi tổng số lượt người tham gia đọc sách.
• Dòng thứ hai ghi số ngày nhiều nhất có cùng lượt người đọc. Trường hợp tất cả các ngày không có cùng lượt người đọc thì ghi -1.

Example

6
15 60 50 25 20 50

220
2

6
15 60 50 25 20 55

225
-1

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài có \(N \leq 10^3\).
• Có \(40\%\) số test khác ứng với \(40\%\) số điểm với trường hợp còn lại.

Viết chương trình nhập từ bàn phím một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\). Hãy tìm và in ra giá trị lớn nhất trong mảng.

Input

• Dòng đầu tiên là số nguyên dương \(n\) - độ dài của dãy \(a\). \((1 \leq n \leq 100)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) - mỗi số cách nhau một dấu cách \((|a_i| \leq 100)\).

Output

Một dòng duy nhất chứa giá trị lớn nhất của mảng.

Example

5
3 2 1 5 2

5

Cho hai số nguyên dương \(n\) và \(g\). Nhiệm vụ của bạn là đếm số lượng các tập con khác rỗng của tập hợp \(\{1, 2, \ldots, n\}\) có ước chung lớn nhất (UCLN) đúng bằng \(g\).

Input

• Dòng duy nhất chứa hai số nguyên \(n\) và \(g\) (\(1 \le g \le n \le 10^6\)).

Output

• In ra một số nguyên duy nhất là đáp án của bài toán, sau khi chia lấy dư cho \(10^9 + 7\).

Example

6 2

5