Servers#2881
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, 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 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 euros 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 computers for installing proxy servers, minimizing the total maintenance costs for all computers.
The first line contains two integers and — the number of computers in the network and the number of proxy servers to be installed (1 \leq k \leq n \leq 2000).
All computers in the network are numbered from to 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 -th computer to the neighboring one with a smaller number, and t_i is the service rate of this computer (2 \leq i \leq n). All l_i and t_i do not exceed 10^6.
On the first line, output the minimum cost of maintaining all computers by all servers. On the second line, output the numbers of the computers where the servers should be installed, separated by spaces. If there are multiple valid configurations, any can be output.
Example 1