История не была закончена, как думал PMP. Бог предложил ему еще один шанс перевоплотиться и вернуться к жизни. Но прежде чем он сможет вернуться, Бог сказал ему, что PMP должен расспросить n великих людей, включая выдающихся программистов, об их жизненном опыте.

Эти люди стоят на одной прямой. Они пронумерованы от 1 до n слева направо. Человек номер i стоит в точке с координатой x_i (x_i < x_i + 1, i < n). PMP должен посетить всех этих людей одного за другим в произвольном порядке. Каждого человека надо посетить ровно один раз. PMP начинает обход, подойдя к месту s-го человека, после чего вступает с ним в разговор и перенимает его опыт.

Каждый раз, когда PMP хочет изменить свою позицию, он должен дать билет ангелу, и ангел относит его к месту назначения. Ангелы берут PMP в одном месте, летят к пункту назначения и приземляют его там. При перемещении они никого не посещают. Перелет от i-го до j-го человека занимает |x_i - x_j| времени. PMP может вернуться к жизни, как только он посетит всех людей.

Есть два вида ангелов: некоторые ангелы летают вправо и принимают только билеты направо. Другие летят налево и принимают только билеты налево. Есть неограниченное количество ангелов каждого типа. PMP имеет l левых билетов и n - 1 - l правых билетов.

PMP хочет вернуться к жизни как можно скорее, чтобы не упустить возможность поучаствовать в финале этого года вместо прошлогоднего финала, который он пропустил. Он хочет узнать самый быстрый способ посетить всех людей ровно по одному разу. Он также должен знать точную последовательность передвижений, которые он должен выполнить.