Trồng dâu

Xem PDF

Điểm: 350 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Laurier vì nghỉ dịch ở nhà nên không có gì làm, vì quá chán nản nên cô bé òa khóc. Rất may là \(2\) người thân của cô ấy (Cô TếchDì Ana) tới nhà chơi và rủ Laurier đi trồng dâu.

Vườn dâu của Cô TếchDì Ana là một hình chữ nhật có dạng ô lưới gồm \(a\) đường kẻ ngang và \(b\) đường kẻ dọc cách nhau \(1\) đơn vị. Các cây dâu chỉ được trồng ở các điểm giao nhau giữa các đường kẻ và bắt buộcngoài viền của vườn và \(2\) cây dâu bất kì phải có khoảng cách ít nhất là \(k\) đơn vị( khoảng cách giữa \(2\) cây dâu là độ dài đoạn thẳng nối chúng ).

Bây giờ Cô TếchDì Ana giao vườn dâu cho Laurier trồng. Laurier phân vân không biết mình sẽ trồng được tối đa bao nhiêu cây dâu, hãy giúp cô ấy nhé !

Input

  • Một dòng duy nhất là \(3\) số nguyên dương \(a,b,k (2 \le k \le a \le b \le 2*10^9)\).

Output

  • Gồm một số nguyên duy nhất là số dâu trồng được tối đa.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(k \le a \le b \le 10^5\).
  • Subtask \(2\) (\(50\%\) số điểm): \(k \le a \le b \le 2*10^9\).

Example

Test 1

Input
2 3 1
Output
6

Test 2

Input
4 4 2
Output
4
Note

Đây là hình mô tả của ví dụ 2:


Bình luận