На прямой есть n человек и k ключей. Каждый из людей хочет попасть в офис, который также расположен на прямой. Для этого каждому человеку нужно сначала дойти до точки, в которой находится ключ, взять его, а затем отправиться в офис. После того как человек взял ключ, больше этот ключ взять никто не сможет.
Перед вами стоит задача определить минимальное время по истечении которого все n людей смогут добраться до офиса с ключами. Считайте, что каждый из людей преодолевает единицу расстояния за 1 секунду. Если в точку с ключом одновременно придут два человека, то ключ может взять только один из них. Человек не обязан брать ключ, мимо которого проходит.
Выходные данные
Выведите минимальное время в секундах по истечении которого все n людей смогут добраться до офиса с ключами.
Примечание
В первом примере человек, находящийся в точке 20 должен взять ключ, находящийся в точке 40 и дойти с ним до офиса, который находится в точке 50. На это он потратит 30 секунд. Человек, находящийся в точке 100 может взять ключ, находящийся в точке 80 и дойти с ним до офиса. На это он потратит 50 секунд. Таким образом, через 50 секунд все люди могут оказаться в офисе с ключами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4 50
20 100
60 10 40 80
|
50
|
|
2
|
1 2 10
11
15 7
|
7
|