A factory produces products as follows. There are N days in the coming production season. Each morning the factory orders materials. At noon the materials will arrive and shipped into a warehouse. In the afternoon the factory produces products using the material in the warehouse. There is only one kind of material and one kind of product, and one unit of materials can make one unit of product. The factory needs to produce exactly di products on the i-th day of the production season, where i is between 1 and N. Also if the factory does not use all the materials in the warehouse, it can use them later, but the material can only be stored in the warehouse for up to 2 days, after that they cannot be used to make products. That is, if a material was shipped to the factory on the i-th day, it can be used only on the i-th and i + 1-th day. We want to order materials for this factory with minimum cost. Let pi be the price of material on the i-th day and ni be the maximum number of units of material one can order on the i-th day. Both pi and ni are changing daily. Note that we may want to order more materials when they are cheap, but keep in mind that we can order at most ni units on the i-th day, and we must use the materials within two days after we order them. Fortunately, the warehouse is large enough to store all materials for the entire production season, so we do not need to worry about its capacity. Instead we only need to determine the amount of materials to order for each day, so that we can produce di products on the i-th day, and the entire material cost is minimized. Technical Specification
2/2 76 9 11 56 6 2 Sample Output 1000 874