Có n ông táo và m bà táo được Ngọc Hoàng phân công nhiệm vụ vào năm mới. Đầu tiên Ngọc Hoàng sẽ chọn k táo (ông và bà) làm nhiệm vụ đặc biệt trên thiên đình. Các ông táo và bà táo còn lại sẽ chia thành các nhóm để phân bố xuống các gia đình ở dưới hạ giới, mỗi nhóm gồm 2 ông táo và 1 bà táo. Hãy xác định số nhóm lớn nhất có thể được phân bố xuống hạ giới.

Input

Gồm 3 số nguyên dương n, m, k (1 <= n, m, k <= 10⁹)

Output

Gồm 1 dòng chứa số nhóm lớn nhất có thể được phân số xuống hạ giới.

Example

Input

6 3 2

Output

2

Cho số tự nhiên ~N~. Hãy tìm số tự nhiên ~K~ nhỏ nhất sao tổng các số lẻ từ ~1~ đến ~K~ lớn hơn tổng các số chẵn từ ~K + 1~ đến ~N~.

Input

• Gồm một dòng chưa số tự nhiên ~N~ ~(N \le 10^9)~.

Output

• Gồm một dòng chứa một số tự nhiên là số ~K~ nhỏ nhất thoả mãn.

Scoring

• Subtask ~1~ (~60~%): ~n \le 1000~
• Subtask ~2~ (~40~%): Không có ràng buộc gì thêm

Ví dụ

Sample Input

10

Sample Output

8

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].

Dữ liệu

Gồm 2 số L, R (1 <= L <= R <= 10^5)

Kết quả

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

Chú ý

Có 50% số test có 1 <= L <= R <= 10^3.

Cho 2 số nguyên dương ~a~ và ~b~

Yêu cầu: Tìm số nguyên dương ~x~ nhỏ nhất sao cho ~a~ ~+~ ~x~ chia hết cho ~b~, và ~b~ ~+~ ~x~ cũng chia hết cho ~a~

Input

• Dòng đầu tiên là 2 số nguyên dương ~a~ và ~b~ ~(a, b \le 10^9)~

Output

Yêu câu của bài toán

Giới hạn

• Giải toán đi chứ không cho cày trâu

Ví dụ

Sample input

6 10

Sample output

14