Банкополис — удивительный город, в котором все n перекрестков расположены на одной прямой, пронумерованы вдоль нее от 1 до n, и на углу каждого из них есть офис банка.

Перекрестки соединены m ориентированными велосипедными дорожками (дорожка номер i ведет от перекрестка u_i к перекрестку v_i), для каждой дорожки известна сложность проезда по ней.

Обычный клиент банка Олег на день рождения этого самого банка решил подарить счастье и радость его работникам. Он хочет посетить ровно k отделений банка и в каждом посещенном отделении подарить всем его работникам подарки.

Проблема в том, что Олег не хочет видеть реакцию на свои подарки, поэтому он не будет пользоваться дорожкой, проходящей мимо офиса, в котором он уже раздавал подарки (формально, дорожка номер i проходит мимо офиса на перекрестке x если и только если min(u_i, v_i) < x < max(u_i, v_i))). Конечно, в каждом офисе Олег может раздавать подарки только один раз. Передвигаться Олег будет по дорожкам, причем он хочет использовать ровно k - 1 дорожку на перемещение между офисами. Олег может начать с любого офиса и закончить поздравлять в любом офисе.

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