The U2 rock group will give a concert in Nicosia during November 96. A queue of n<=200
U2fans 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 ith fan (where 1 <= i <=
n). However, two consecutive fans in the queue (e.g. the jth and the (j+1)th one (1
<= j <= n1) 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 jth and the (j+1)th fan
is smaller than t_{j} + t_{j+1}. Thus, in order to minimize the cashier's
time and prevent the U2fans 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, t_{i} and r_{j}, 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.
Input: Your program should read the input file named INPUT.TXT. Input data consists of three lines:


Output: 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 ith fan is served alone, or i+(i+1) if these two fans are served as a pair. 

Example:

Time Limit: 15 sec
Maximum Score : 35