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

Một công ty đồ chơi nhập khẩu \(n\) con búp bê gỗ, được đánh số từ \(1\) đến \(n\). Mỗi con búp bê thứ \(i\) có kích thước là một số nguyên dương \(a_i\). Một con búp bê thứ \(i\) có thể được lồng vào bên trong một con búp bê thứ \(j\) nếu con búp bê thứ \(j\) đang rỗng và kích thước của chúng thỏa mãn điều kiện \(a_i + k \le a_j\), trong đó \(k\) là một hằng số nguyên dương cho trước.

Khi các con búp bê được lồng vào nhau, công ty chỉ cần tìm chỗ đặt cho những con búp bê ngoài cùng (những con không được lồng vào bất kỳ con búp bê nào khác).

Yêu cầu:
Hãy tìm cách lồng các con búp bê vào nhau sao cho tổng kích thước của tất cả các con búp bê ngoài cùng là nhỏ nhất.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn (stdin) 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^9\)), cách nhau bởi một dấu cách.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^9\)), cách nhau bởi một dấu cách.

Output

In ra một số nguyên duy nhất là tổng kích thước nhỏ nhất của các con búp bê ngoài cùng.

Example

8 2
8 4 2 1 1 3 5 9

18

Scoring

\begin itemize

• Có 30% số điểm ứng với \(n \le 10\).
• 70% số điểm còn lại không có ràng buộc gì thêm.
  \end itemize

Một số nguyên dương được gọi là số "đặc biệt" nếu số đó có đúng 3 ước nguyên dương đồng thời khác nhau.

**Yêu cầu:** Cho $M$ cặp số nguyên dương $(a; b)$, hãy đếm số lượng số "đặc biệt" $x$ thoả mãn $a \leq x \leq b$.

Yêu cầu: Cho \(M\) cặp số nguyên dương \((a; b)\), hãy đếm số lượng số "đặc biệt" \(x\) thoả mãn \(a \leq x \leq b\).

Input

Từ file SNUM.INP gồm:

• Dòng đầu là số nguyên dương \(M\) (\(1 \leq M \leq 10^5\));
• \(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(a, b\) cách nhau bởi một khoảng trắng (\(1 \leq a \leq b \leq 10^6\)).

Output

Ghi ra file SNUM.OUT gồm \(M\) dòng, mỗi dòng là kết quả tương ứng tìm được.

Example

2
1 10
1 100

2
4

Scoring

• Có \(20\%\) số điểm ứng với (\(1 \leq M \leq 10^2; 1 \leq b \leq 10^2\));
• Có \(30\%\) số điểm ứng với (\(1 \leq M \leq 10^3; 1 \leq b \leq 10^3\));
• \(50\%\) số điểm còn lại không có giới hạn gì thêm.

Một nhóm thợ có \(n\) công việc cần làm, mỗi công việc mất một số giờ nhất định để hoàn thành. Công việc thứ \(i\) mất \(a_i\) giờ.

Bạn được yêu cầu chia các công việc này thành \(k\) đoạn liên tiếp (các công việc trong cùng một đoạn phải liền kề nhau). Mỗi đoạn sẽ được giao cho một người thợ.

Nhiệm vụ của bạn là chia sao cho thời gian làm việc lâu nhất trong số \(k\) thợ là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \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)\) --- thời gian cần để hoàn thành công việc thứ \(i\).

Output

In ra một số nguyên --- thời gian làm việc lâu nhất mà một người thợ phải thực hiện, nếu chia công việc theo cách tối ưu.

Example

5 3
2 4 7 3 5

8

Scoring

• Subtask 1 (20 điểm): \(k = 2\)
• Subtask 2 (30 điểm): \(k = 3\)
• Subtask 3 (50 điểm): Không có ràng buộc gì thêm.