Po có hai đống sỏi, đống thứ nhất có $a$ viên, đống thứ hai có $b$ viên. Ở mỗi lượt chơi, Po có thể chọn một số nguyên dương $x_i$ trong đoạn $[1,k]$ rồi bỏ đi $x_i$ viên sỏi ở cả hai đống, tất nhiên mỗi đống phải có số viên sỏi không nhỏ hơn $x_i$. Số $x_i$ được chọn ở các lượt chơi phải khác nhau.

Trò chơi kết thúc khi Po không thể thực hiện thêm lượt chơi.

Yêu cầu: Hãy cho biết tổng số viên sỏi ít nhất có thể sau khi trò chơi kết thúc.

Dữ liệu vào

• Ba số nguyên dương lần lượt là $a,b,k$

Kết quả

• Tổng nhỏ nhất có thể của hai đống sỏi sau khi trò chơi kết thúc.

Ví dụ:

Input

4 5 2 

Output

3 

Ràng buộc:

• sub1: có 50% số test có $a,b,k≤10^6$
• sub2: 50% số test còn lại có $a,b≤10^{18};$ $k≤10^9$