У Vitaly503 сегодня оказалась клетчатая доска со стороной \(n\), а также \(k\) фишек. Vitaly503 понял, что все эти \(k\) фишек нужно расположить на клетках доски (на одну клетку можно размещать не более одной фишки).
Обозначим ячейку в \(i\)-й строке и \(j\)-м столбце как \((i ,j)\). Диагональ – это набор ячеек, для которых значение \(i + j\) одинаково. Например, клетки \((3, 1)\), \((2, 2)\) и \((1, 3)\) лежат на одной диагонали, но \((1, 2)\) и \((2, 3)\) не лежат на одной диагонали. Диагональ называется занятой, если она содержит хотя бы одну фишку.
Vitaly503 просит вас помочь ему и сообщить минимальное количество занятых диагоналей, которое он может получить после размещения всех \(k\) фишек.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество диагоналей с хотя бы одной фишкой, которое он может получить после размещения всех \(k\) фишек.
Примечание
В первом наборе входных данных фишек нет, поэтому будут заняты 0 диагоналей. Во втором наборе входных данных обе фишки можно разместить на диагонали \((2, 1), (1, 2)\), поэтому ответ — 1. В третьем наборе входных данных 3 фишки нельзя разместить на одной диагонали, но размещение их на \((1, 2), (2, 1), (1, 1)\) делает 2 диагонали занятыми. В 7-м наборе входных данных фишки займут все 5 диагоналей в любой допустимой расстановке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 0
2 2
2 3
2 4
10 50
100 239
3 9
|
0
1
2
3
6
3
5
|