Монокарп нашел карту сокровищ. Карта показывает местоположение сокровища на оси OX. Монокарп находится в точке \(0\), сундук сокровищ находится в точке \(x\), ключ от сундука находится в точке \(y\).
Очевидно, Монокарп хочет открыть сундук. Он может выполнять следующие действия:
- пойти на \(1\) влево или \(1\) вправо (затратив \(1\) секунду);
- поднять ключ или сундук, если Монокарп находится в той же точке, что и объект (затратив \(0\) секунд);
- опустить сундук в текущей точке (затратив \(0\) секунд);
- открыть сундук, если Монокарп находится в той же точке, что и сундук, и он подобрал ключ ранее (затратив \(0\) секунд).
Монокарп может нести сундук, но сундук довольно тяжелый. Монокарп знает, что может нести его суммарно не более \(k\) секунд (его выносливость не сбросится, если он поднимет и опустит сундук).
Какое минимальное время потребуется Монокарпу, чтобы открыть сундук?
Выходные данные
Для каждого теста выведите одно целое число — минимальное время, необходимое Монокарпу, чтобы открыть сундук.
Примечание
В первом наборе входных данных Монокарп может открыть сундук за \(7\) секунд с помощью следующей последовательности действий:
- пойти \(5\) раз вправо (\(5\) секунд);
- поднять сундук (\(0\) секунд);
- пойти \(2\) раза вправо (\(2\) секунды);
- поднять ключ (\(0\) секунд);
- опустить сундук (\(0\) секунд);
- открыть сундук (\(0\) секунд).
Он несет сундук только \(2\) секунды, что не превышает его выносливости.
Во втором наборе Монокарп может поднять ключ по пути к сундуку.
В третьем наборе Монокарп не может использовать стратегию из первого тестового случая, потому что он должен был бы нести сундук в течение \(3\) секунд, в то время как его выносливости хватает только на \(2\) секунды. Таким образом, он несет сундук до \(7\), опускает его, идет на \(1\) вправо, чтобы поднять ключ, и возвращается на \(1\) влево, чтобы открыть сундук.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 7 2
10 5 0
5 8 2
|
7
10
9
|