Задача состоит из трех подзадач: за решение подзадачи С1 вы получите 4 балла, за решение подзадачи С2 вы получите 4 балла, за решение подзадачи C3 вы получите 8 баллов.

Манао решил заняться борьбой на профессиональном уровне. Для своего дебюта он избрал уже начавшийся турнир. До того, как Манао вступил в него, в турнире было n участников, пронумерованных от 1 до n. У каждого из них было некоторое количество очков. Более конкретно, у i-го участника было p_i очков.

Манао будет бороться с каждым из участников ровно один раз. Каждый из поединков заканчивается для него или победой, или поражением. Каждая победа Манао прибавляет к его счету 1 очко, а каждое его поражение прибавляет 1 очко к счету соответствующего противника. Для каждого i, Манао определил степень усилий e_i, которую ему нужно приложить, что победить в бою против i-го участника. Проиграть бой усилий не требует.

После окончания всех боев с участием Манао будет сгенерирована турнирная таблица. Стандартно, самое лучшее место в турнирной таблице — первое, а самое худшее — место n + 1. Участники турнира будут упорядочены по убыванию набранных ими очков. Участники, имеющие равный счет с Манао, будут иметь ранг лучше него, если их единственный бой закончился поражением Манао, и хуже в противном случае. Как именно производится ранжировка других участников с одинаковым количеством очков, для этой задачи значения не имеет.

Цель Манао — получить место k или лучше. Определите минимальную суммарную степень усилий, которую ему надо приложить для достижения своей цели, если это вообще возможно.