The U2 rock group will give a concert in Nicosia during November 96. A queue of n<=200 U2-fans waiting to buy a ticket from a single cashier has been formed. Each person wants to buy only one ticket, whereas the cashier can sell at most two tickets to a person.
Suppose that the cashier spends ti time units to serve the i-th fan (where 1 <= i <= n). However, two consecutive fans in the queue (e.g. the j-th and the (j+1)-th one (1 <= j <= n-1) may agree so that one of them remains in the queue and the other leaves the queue, if the time rj required by the cashier to serve the j-th and the (j+1)-th fan is smaller than tj + tj+1. Thus, in order to minimize the cashier's time and prevent the U2-fans from being squeezed, each person in the queue tries to negotiate with his predecessor and his successor, and finally speed up the process.
Given positive integer values for n, ti and rj, minimize the total cashier's time. This is achieved by making pairs of consecutive persons in an optimal way. Note, however, that it is not necessary for a specific fan to be paired with a predecessor or a successor.
Your program should read the input file named INPUT.TXT. Input data consists of three lines:
The first line of the file named OUTPUT.TXT contains an integer which represents the total cashier's time. Each one of the next lines contains either 1 number or 2 numbers separated by the character +. More specifically, each line contains the number i, if the i-th fan is served alone, or i+(i+1) if these two fans are served as a pair.
Time Limit: 15 sec
Maximum Score : 35