Lõi năng lượng của phi thuyền có mức năng lượng là một số nguyên dương N. Để tránh quá tải cục bộ, bạn cần phân rã N thành tổng của một tập hợp các số nguyên dương phân biệt (không có 2 số nào giống nhau). Hệ thống yêu cầu tập hợp này phải chứa số lượng các con số là nhiều nhất có thể. Hãy in ra số lượng đó.

Input: Số nguyên dương N (1 <= N <= 10^9).

Output: Số lượng các số nguyên dương phân biệt nhiều nhất có tổng bằng N.

Ví dụ:

Input:

12

Output:

4

(Giải thích: 12 có thể tách thành 1 + 2 + 3 + 6. Số lượng là 4 số).

Buổi dạ hội có N nam và M nữ. Chiều cao của nam thứ i là Ai, của nữ thứ j là Bj. Hai người có thể ghép thành một cặp khiêu vũ nếu mức độ chênh lệch chiều cao giữa họ không vượt quá K (tức là |Ai - Bj| <= K). Mỗi người chỉ được ghép tối đa 1 cặp. Hãy tìm số lượng cặp khiêu vũ lớn nhất có thể tạo ra.

Input:

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

Dòng 2: N số nguyên A_i.

Dòng 3: M số nguyên B_j.

Output: Số cặp tối đa.

Ví dụ:

Input:

4 5 1
1 4 6 9
2 5 7 8 10

utput:

4

(Giải thích: Ghép (1,2), (4,5), (6,7), (9,8) hoặc (9,10)).

Có N bộ quần áo ướt, bộ thứ i chứa A_i lượng nước. Nếu để khô tự nhiên, mỗi phút mỗi bộ giảm 1 lượng nước. Bạn có một chiếc máy sấy, mỗi phút chỉ sấy được 1 bộ quần áo. Khi dùng máy sấy, bộ quần áo đó sẽ giảm K lượng nước trong phút đó (các bộ khác vẫn khô tự nhiên giảm 1). Hãy tính thời gian (số phút) ít nhất để tất cả quần áo đều khô hoàn toàn (lượng nước <= 0).

Input:

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

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

Output: Số phút ít nhất cần thiết.

Ví dụ:

Input:

3 5
2 3 9

Output:

3

(Giải thích: Phút 1: sấy áo 3 (còn 4), áo 1,2 khô tự nhiên (còn 1,2). Phút 2: sấy áo 3 (còn -1), áo 1,2 tự nhiên (còn 0,1). Phút 3: sấy áo 2 (còn -4), áo 1 (đã khô). Tổng 3 phút).

Trên bàn cờ kích thước N x M, một quân Mã xuất phát tại ô (1, 1) và cần đi đến ô (N, M). Do quân Mã này bị thương nên nó chỉ có thể di chuyển theo hướng tiến lên: Từ ô (i, j) chỉ được nhảy đến ô (i+1, j+2) hoặc (i+2, j+1). Có một số ô bị đặt bẫy không thể nhảy vào. Hãy đếm số cách để quân Mã đến được đích (kết quả chia dư cho 10^9+7).

Input:

Dòng 1: N, M, K (1 <= N, M <= 1000, 0 <= K <= 10^4). (K là số lượng bẫy).

K dòng tiếp theo: Mỗi dòng tọa độ x, y của bẫy.

Output: Số cách di chuyển modulo 10^9+7.

Ví dụ:

Input 01:

4 4 0

Output 01:

2

(Giải thích: Cách 1: (1,1) -> (2,3) -> (4,4). Cách 2: (1,1) -> (3,2) -> (4,4)).

Input 02:

4 4 1
2 3

Output 02:

1