Servers
In a certain house, a computer network was established by connecting each new computer to the last one already connected. Once connected, no two computers were linked to each other again. In total, n computers were connected sequentially. Neighbors exchanged information among themselves, but eventually realized they needed proxy servers. The residents decided to install proxy servers on exactly k computers. The remaining decision is which computers to choose for this purpose. The main goal is to minimize the monthly cost of maintaining all computers with servers.
Each computer has a service rate, expressed in rubles per meter of wire. The cost of servicing a computer by a server is calculated as the computer's rate multiplied by the total length of the wire from that computer to the server that services it.
Your task is to write a program that selects k computers for installing proxy servers, minimizing the total maintenance costs for all computers.
Input
The first line contains two integers n and k - the number of computers in the network and the number of proxy servers to be installed (1 ≤ k ≤ n ≤ 2000).
All computers in the network are numbered from 1 to n in the order of connection.
The second line contains one integer t_{1} - the service rate of the first computer.
In the next n - 1 lines, each line contains two non-negative integers l_{i} and t_{i} - information about the other computers in the network in order of their numbers. l_{i} is the length of the wire connecting the i-th computer to the neighboring one with a smaller number, and t_{i} is the service rate of this computer (2 ≤ i ≤ n). All l_{i} and t_{i} do not exceed 10^6.
Output
On the first line, output the minimum cost of maintaining all computers by all servers. On the second line, output the k numbers of the computers where the servers should be installed, separated by spaces. If there are multiple valid configurations, any can be output.