## CCO Preparation Test 3 - Packing Up

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

Bruce is going to Waterloo to watch CCO. He needs to pack up all of his books. There are books, which are numbered from to . Bruce has a super compressor, which will compress the book into one dimension with length . After compressing, Bruce will put his books into a number of one dimensional containers. Since Bruce doesn't want to mess up the order of his books, he has to pack up books in the order from to . Bruce can pack one book into one container or multiple books into one container. If multiple books are placed into one container, Bruce will insert a separator with unit length between any two consecutive books. Bruce wants all separators to separate two books from each other, and there should only be one separator between two adjacent books. Thus, the length of the container for holding book to book will be . The cost of a container is calculated by , where is the container's length and is a given constant. Bruce can buy containers with arbitrary lengths from the supermarket. But Bruce wants to pay the minimal cost. Could you please help Bruce to find the minimal cost of containers to pack up all his books?

#### Input Specification

The first line of input will consist two integers, and .
Each of the following lines will consist of one integer , the length of book .

#### Output Specification

Output one integer, the minimal cost Bruce needs to pay for all the containers. It is guaranteed that Bruce will not pay more than in total.

#### Sample Input

5 4
3
4
2
1
4

#### Sample Output

1

#### Explanation of Output for Sample Input

Bruce can pack book 1 into container 1 with a cost of , book 2 into container 2 with a cost of , book 3 and book 4 into container 3 with a cost of (since there is a separator between book 3 and book 4), and finally book 5 into container 4 with a cost of . The total cost is 1.