Дома у Фродо собираются ночевать n хоббитов. У Фродо есть n кроватей, стоящих в ряд, и m подушек (n ≤ m). Каждому хоббиту для сна нужна кровать и хотя бы одна подушка, однако, каждый хочет как можно больше подушек. Понятно, что подушки не всегда можно поделить поровну, однако любой хоббит обидится, если у него будет меньше подушек, чем у соседа, хотя бы на две.
Фродо будет спать на k-й с краю кровати. Какое максимальное число подушек он может положить себе, чтобы у каждого хоббита была хотя бы одна подушка, все подушки были розданы хоббитам, и никто из них не обиделся?
Выходные данные
Выведите одно число — максимальное число подушек, которые Фродо может положить себе, чтобы никто не обиделся.
Примечание
В первом примере Фродо может взять себе максимум две подушки. Тогда, например, хоббит, который будет спать на первой кровати, может также взять себе две подушки, а хоббиты, которые будут спать на третьей и четвертой кровати, могут взять себе по одной подушке.
Во втором примере Фродо может взять себе максимум четыре подушки. Тогда остальные хоббиты должны будут взять себе по три подушки.
В третьем примере Фродо может взять три подушки себе, дав две подушки хоббиту, спящему посередине, и одну подушку хоббиту на третьей кровати.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6 2
|
2
|
|
2
|
3 10 3
|
4
|
|
3
|
3 6 1
|
3
|