Bài tập

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.

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.

Bình và An đang ôn thi vào trường THPT chuyên. Bình định nghĩa "số đẹp" là số không có chữ số 0 ở tận cùng. Cho hai số nguyên dương \(a, b\) (\(a < b\)), đặt \(S = a \times (a+1) \times \cdots \times b\). Hãy đếm số chữ số 0 tận cùng của \(S\) cần xóa để \(S\) trở thành số đẹp.

Input

Tệp SODEP.INP gồm:

• Dòng 1: Số nguyên \(T\) (\(1 \leq T \leq 10^5\)) - số lượng test cases
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số \(a, b\) (\(a < b \leq 10^{16}\))

Output

Tệp SODEP.OUT gồm \(T\) dòng, mỗi dòng là số chữ số 0 tận cùng của \(S\) tương ứng, lấy modulo \(10^9 + 7\).

Example

4
1 6
1 10
2 4
10 20

1
2
0
3

Scoring

• 40% test: \(T \leq 10\), \(b \leq 18\)
• 30% test: \(T = 1\), \(b \leq 10^5\)
• 20% test: \(T \leq 10^4\), \(b \leq 10^5\)
• 10% test: \(T \leq 10^5\), \(b \leq 10^{16}\)

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