Bankopolis是一个不可思议的城市，所有的n个十字路口都位于一条直线上，沿着这条直线从1到n编号。每个十字路口都有一个银行办公室。
十字路口与m条定向自行车道相连（第i条车道从十字路口ui到十字路口vi），每条车道的难度是已知的。
银行客户奥列格希望给银行员工带来幸福和快乐。他想参观k个办公室，在每个办公室他都想给员工送礼物。
问题是，奥列格不想看到对他的礼物的反应，所以他不能使用经过他已经赠送礼物的办公室附近的自行车道（正式地，第i条车道在第x个十字路口经过办公室附近，如果且仅当min(ui, vi) < x < max(ui, vi))。
当然，在每个办公室，奥列格都可以赠送一次礼物。Oleg将使用k - 1条自行车道，可在办公室之间移动。奥列格可以从任何办公室开始他的道路，并在任何办公室完成。
Bankopolis is an incredible city in which all the
n crossroads are located on a straight line and numbered from
1 to
n along it. On each crossroad there is a bank office.
The crossroads are connected with
m oriented bicycle lanes (the
i-th lane goes from crossroad
ui to crossroad
vi), the difficulty of each of the lanes is known.
Oleg the bank client wants to gift happiness and joy to the bank employees. He wants to visit exactly
k offices, in each of them he wants to gift presents to the employees.
The problem is that Oleg don't want to see the reaction on his gifts, so he can't use a bicycle lane which passes near the office in which he has already presented his gifts (formally, the
i-th lane passes near the office on the
x-th crossroad if and only if
min(ui,vi)<x<max(ui,vi))). Of course, in each of the offices Oleg can present gifts exactly once. Oleg is going to use exactly
k-1 bicycle lane to move between offices. Oleg can start his path from any office and finish it in any office.
Oleg wants to choose such a path among possible ones that the total difficulty of the lanes he will use is minimum possible. Find this minimum possible total difficulty.
Output
In the only line print the minimum possible total difficulty of the lanes in a valid path, or
-1 if there are no valid paths.
Note
In the first example Oleg visiting banks by path
1→6→2→4.
Path
1→6→2→7 with smaller difficulity is incorrect because crossroad
2→7 passes near already visited office on the crossroad
6.
In the second example Oleg can visit banks by path
4→1→3.