405036: GYM101745 A Police Patrol

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Police Patroltime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Nswill consists of n houses arranged in a row and numbered from 1 to n. One patrol car can be responsible for some segment of length no more than k. For example, segment of houses from some l to l + k - 1 inclusive. That means, if any crime happens in a single house on this segment corresponding police patrol will immediately start investigation.

Safety requirements say that the patrols should be assigned in such a way, that if two crimes happen simultaneously in any two different houses, there will be two distinct patrols that can immediately take care of them.

What is the minimum required number of patrols to ensure safety in Nswill?

Input

The only line of the input contains two integers n and k (2 ≤ k ≤ n ≤ 109) — the number of houses in Nswill and the maximum length of a segment that one police patrol can take care of.

Output

Output a single integer, the minimum number of patrols required.

ExamplesInput
5 5
Output
2
Input
3 2
Output
2
Input
4 2
Output
3
Input
7 4
Output
4
Note

In the first sample, we can have both patrols cover the entire neighborhood.

For the second sample, we can have one patrol cover houses 1 and 2, while the other patrol covers houses 2 and 3.

For the third sample, we can have one patrol cover houses 1 and 2, another one cover 2 and 3, while the last cover 3 and 4. For example, if a crime occurs in houses 3 and 4, we can have the second patrol investigate house 3 and the third patrol investigate house 4.

For the last sample, one example of 4 patrols that work is the first and second patrol covers houses 1, 2, 3 and 4, and the third and fourth patrol cover houses 4, 5, 6 and 7.

加入题单

上一题 下一题 算法标签: