Tại trường Đại học Cảnh sát nhân dân, ban chỉ huy cần phân công N học viên đi tuần tra đêm. Các học viên sẽ được ghép thành các tổ tuần tra, mỗi tổ tối đa 2 người. Học viên thứ i có chỉ số sức mạnh là S_i. Để đảm bảo tổ tuần tra không quá phô trương, tổng sức mạnh của 1 tổ không được vượt quá giới hạn C. Hãy tính số lượng tổ tuần tra ít nhất cần thiết để tất cả N học viên đều được phân công. (Biết rằng không có học viên nào có sức mạnh vượt quá C).

Input:

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

Dòng 2: N số nguyên Si (1 <= Si <= C).

Output: Số tổ tuần tra tối thiểu.

Ví dụ:

Input:

4 5
1 2 4 3

Output:

2

Cho một mảng A gồm N số nguyên dương và một số K. Một đoạn con liên tiếp của mảng được coi là "đoạn con chuẩn mực" nếu tổng các phần tử trong đoạn con đó chia hết cho K. Hãy đếm xem có tất cả bao nhiêu "đoạn con chuẩn mực" trong mảng A.

Input:

Dòng 1: N, K (1 <= N <= 10^5, 1 <= K <= 10^5).

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

Output: Số lượng đoạn con thỏa mãn.

Ví dụ:

Input:

5 3
3 1 2 5 1

Output:

5

(Giải thích: Các đoạn con là: [3], [1, 2], [3, 1, 2], [2, 5, 1], [1, 2, 5, 1]).

Có N ca trực ban được đề xuất. Ca trực thứ i bắt đầu tại thời điểm Li và kết thúc tại thời điểm Ri. Một học viên chỉ có thể nhận các ca trực không bị trùng lặp thời gian với nhau (nếu ca 1 kết thúc lúc X và ca 2 bắt đầu lúc X thì vẫn được tính là hợp lệ). Hãy tìm số lượng ca trực tối đa mà một học viên có thể nhận được.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Li, Ri (0 <= Li < Ri <= 10^9).

Output: Số lượng ca trực tối đa.

Ví dụ:

Input:

4
1 3
2 5
4 7
6 9

Output:

3

Hội trường lớn có phần sân khấu hình chữ nhật kích thước 3 x N (3 hàng, N cột). Ban tổ chức muốn lát kín sân khấu này bằng các viên gạch hình chữ nhật kích thước 1 x 2 (có thể đặt nằm dọc hoặc nằm ngang). Hãy đếm số cách khác nhau để lát kín toàn bộ sân khấu. Kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho 10^9+7.

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

Output: Số cách lát gạch modulo 10^9+7.

Ví dụ:

Input:

2

Output:

3

Cho N điểm nguyên trên mặt phẳng. Hai điểm bất kỳ không trùng nhau. Hãy đếm xem có bao nhiêu bộ 3 điểm tạo thành một tam giác vuông.

Đầu vào: Số nguyên N (3 <= N <= 500). N dòng sau chứa tọa độ x, y (-10^4 <= x, y <= 10^4).

Đầu ra: Một số nguyên là số lượng tam giác vuông đếm được.

Ví dụ

Input:

4
0 0
0 2
2 0
2 2

Output:

4