На протяжении 10 лет автолюбитель Кодзиро собирал деньги на свою любимую машину марки Furrari. Наконец заветная мечта Кодзиро сбылась! Теперь Кодзиро хочет доехать до своей подруги Йоханны, чтобы похвастаться перед ней своей машиной.

Кодзиро хочет доехать до подруги, поэтому он будет ехать к ней по числовой прямой. Для простоты можно считать, что Кодзиро находится в точке с абсциссой f числовой прямой, а Йоханна — в точке с абсциссой e. В некоторых точках числовой прямой находятся бензозаправки. На каждой бензозаправке заправляют только одним видом топлива: Регуляр-92, Премиум-95 или Супер-98. Таким образом, каждая заправка характеризуется парой целых чисел t_i и x_i — номером типа бензина и своей позицией.

Одного литра бензина достаточно, чтобы проехать ровно 1 км (эта величина не зависит от типа бензина). Бензины трех видов отличаются лишь качеством, которое по данным исследований влияет на время жизни двигателя автомобиля. Бак Furrari вмещает ровно s литров бензина (независимо от типа бензина). В момент выезда из точки f бак Кодзиро полностью заполнен бензином марки Супер-98. На каждой заправке Кодзиро может заправить бак любым количеством бензина, но, конечно, ни в какой момент времени количество бензина в баке не может стать больше s литров. Обратите внимание, что в баке может одновременно находиться бензин разных типов. Машина может двигаться как влево, так и вправо.

Для продления времени жизни двигателя Кодзиро старается в первую очередь минимизировать количество бензина типа Регуляр-92. Если существует несколько стратегий проехать из f в e, использовав минимальный объем бензина типа Регуляр-92, то надо проехать так, чтобы минимизировать использованный объем бензина Премиум-95.

Напишите программу, которая для m возможных положений старта f_i минимизирует объем потраченного бензина типа Регуляр-92 и объем потраченного бензина типа Премиум-95 во вторую очередь.