Bài tập

Bạn được cung cấp \(N\) đoạn dây, với \(1 \le N \le 10^5\). Đoạn dây thứ \(i\) có độ dài \(a_i\), với \(0 < a_i \le 10^9\).

Cần cắt các đoạn dây này thành \(K\) đoạn có độ dài bằng nhau, với \(K\) là một số nguyên dương. Các đoạn dây ban đầu có thể không cần được sử dụng hết. Phần thừa từ các đoạn dây bị cắt có thể bỏ đi.

Hãy xác định độ dài lớn nhất của đoạn dây mà bạn có thể thu được sau khi cắt, sao cho có thể tạo ra ít nhất \(K\) đoạn như vậy. Nếu không có cách nào để cắt được \(K\) đoạn có độ dài nguyên dương, hãy in ra \(0\).

Input

Dữ liệu vào được cung cấp từ bàn phím theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) (\(N \le 10^5, K \le 10^{14}\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(a_i\), là độ dài của đoạn dây thứ \(i\).

Output

In ra một dòng duy nhất chứa độ dài lớn nhất của đoạn dây có thể nhận được.

Example

4 11
802
743
547
539

200

Bạn được cho một mảng gồm \(n\) số nguyên dương. Bạn cần biến đổi sao cho mảng này được sắp xếp theo trình tự tăng dần, và mọi phần tử trong mảng đều không nhỏ hơn phần tử đứng trước.

Trong mỗi lần biến đổi, bạn có thể tăng một phần tử lên một đơn vị. Hãy tìm số lần biến đổi ít nhất để thoả mản điều kiện trên.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\).

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) --- giá trị của mảng \(a\).

Output

• In ra số lần biến đổi ít nhất.

Example

5
3 2 5 1 7

5

Cho một mảng gồm \(n\) số nguyên và số nguyên \(t\).

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá \(t\). Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,t(1\le n\le 10^5;1\le t\le 10^9)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^4)\)

Output

• In ra giá trị cần tìm.

Example

4 4
1 2 1 2

3

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\).