4th Balkan Olympiad in Informatics
Nicosia, Cyprus, 19-25 October 1997

Day 2 - Problem 1 (Waiting for a ticket)

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 t_j + t_j+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, 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: The first line contains the integer n The second line contains n integers the ti values separated by spaces The third line contains n-1 values standing for the rj values separated by spaces
	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 i-th fan is served alone, or i+(i+1) if these two fans are served as a pair.
	Example: Input: 7 5 4 3 2 1 4 4 7 3 4 2 2 4 Output: 14 1 2+3 4+5 6+7

Time Limit: 15 sec
Maximum Score : 35