Tin học trẻ 07.03

Ba anh em An, Bình, Phúc được mẹ mua cho ba hộp bi có số viên bi tương ứng là \(a, b, c\) (số bi trong mỗi hộp khác nhau). Bình biết anh An sẽ nhường cho mình lấy hộp có số bi nhiều hơn và Bình cũng sẽ nhường em Phúc hộp có số bi nhiều nhất.

Hãy viết chương trình nhập vào ba số nguyên có giá trị đôi một khác nhau tương ứng với số bi trong ba hộp mà mẹ mua, chương trình sẽ trả về số bi mà Bình được nhận. (Số bi trong mỗi hộp không vượt quá \(100\))

Example

5 3 4

4

Trong nhà Nam hiện đang có n ổ cắm điện rời. Số lượng chỗ cắm trên mỗi ổ cắm điện này lần lượt là \(a_1,a_2,a_3,…,a_n\) chỗ cắm. Trên tường nhà Nam có một chỗ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện.

Nam có m thiết bị sử dụng điện, để sử dụng thì các thiết bị này cần được cắm vào ổ cắm trên tường hoặc ổ cắm rời đang có điện. Bạn hãy giúp Nam tìm ra số ổ cắm rời ít nhất cần dùng để có thể sử dụng tất cả m thiết bị điện này.

Input

• Dòng thứ nhất gồm 2 số nguyên n,m cách nhau một khoảng trắng, dữ liệu vào đảm bảo \(1 ≤ n,m ≤ 10000, n\) là số lượng ổ cắm và \(m\) là số lượng thiết bị.
• Dòng thứ hai gồm n số nguyên \(a_1,a_2,a_3,…,a_n\) là số chỗ cắm trên các ổ cắm rời tương ứng, mỗi số cách nhau một khoảng trắng, dữ liệu vào đảm bảo \(1 ≤ a_i ≤ 50\).

Output

• Là số nguyên cho biết số ổ cắm rời ít nhất cần sử dụng là bao nhiêu. Nếu đã sử dụng hết tất cả ổ cắm rời mà vẫn không đủ, in ra \(−1\).

Example

3 4
3 2 2 

2

4 7
3 3 2 4 

3

Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1; 3; 5; 7; …\). Một tháp ô vuông có \(n\) hàng gọi là tháp ô vuông bậc \(n\) (\(n\) là số tự nhiên).

Ví dụ ở hình vẽ sau ta có một tháp ô vuông bậc \(3\):

Yêu cầu: Cho trước một tháp ô vuông bậc \(n\). Hãy tính xem trong tháp ô vuông này có tất cả mấy hình vuông tạo thành từ các ô vuông đó.

Input

• Chứa một số \(n\) (\(n \le 5 \times 10^5\)).

Output

• Ghi ra số nguyên \(m\) là số các hình vuông cần tìm.

Example

3

11

Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số \(12\) có tổng các ước số (không kể \(12\)) là \(1 + 2 + 3 + 4 + 6 = 16 > 12\). Do đó \(12\) là một số phong phú.

Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [\(L,R\)].

Input

• Gồm 2 số \(L, R\) (\(1 \leq L \leq R \leq 10^6\))

Output

• Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [\(L, R\)].

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq L \leq R \leq 10^3\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm

Example

1
50

9