The festival sound engineer claims the main stage has a "perfect loop": every time you listen to any ~k+1~ consecutive beats on the circular playlist, the XOR of those beats is exactly ~0~. The headliner, Oxenfree, swears this is not witchcraft, just math and a lot of drum machines.

You, a rookie producer, are trying to recreate this effect in one of your new songs. Given integers ~n~, the total length of your song, and ~k~, the number of elements considered before each element in a "perfect loop", you must consider the binary sequence ~a_0, a_1, \dots, a_{n-1}~ arranged circularly (as the track plays on loop). Indices are thus taken modulo ~n~, i.e., index ~n~ is the first element.

The loop condition you are looking for to recreate the viral effect is:

$$\displaystyle a_i \oplus a_{i-1} \oplus a_{i-2} \oplus \cdots \oplus a_{i-k} = 0 \ \text{ for all }\ i, $$

where ~\oplus~ is XOR over bits.

Among all sequences that satisfy the loop condition, find the maximum possible number of ~1~s in the sequence, as this represents the loudest possible such song. You only need to output this maximum count, not the sequence itself, and then maybe your song will go viral and be played on the main stage too.

Input

The input consists of a single line containing two integers ~n~ and ~k~ ~(2 \leq n \leq 10^9~, ~1 \leq k \leq n-1)~ — the number of elements in the binary sequence representing your song and the number of elements before each element considered in the "perfect loop" (i.e. the length of each loop minus one).

Output

Output a single integer — the maximum number of ones in a valid length-~n~ sequence. It is always possible to find such a sequence as one with all zeros will always be valid for any ~k~.

Examples

Input 1

5 2

Output 1

0

The all-zero sequence ~00000~ satisfies the condition because every XOR of three consecutive bits is ~0~. Adding any ones will ruin this, so this is the maximum case.

Input 2

6 2

Output 2

4

One valid sequence is ~110110~. For ~k=2~ the condition is ~a_i \oplus a_{i-1} \oplus a_{i-2} = 0~, which is equivalent to ~a_i = a_{i-1} \oplus a_{i-2}~. This sequence follows that rule, and it can be shown that no sequence with more than ~4~ ones does.

Input 3

8 3

Output 3

8

Input 4

10 4

Output 4

8