CF793D Presents in Bankopolis

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 $ u_{i} $ to crossroad $ v_{i} $ ), 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(u_{i},v_{i})<x<max(u_{i},v_{i}))) $ . 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.

N/A

N/A

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 $ .