Appu and Sugarcane Farm-2

0

0 votes
Problem

Appu is now frustrated,because even after using the height doubling powder from the market, he is unable to normalize the heights of sugarcanes. Since Appu is very very stubborn, he will find a way to normalize the heights of sugarcanes by hook or crook.

Luckily Appu came to know about this "Organic Adhesive" which can combine two pieces of sugarcane at the joints. Appu's sugarcanes are made up of individual units of length L joined together at joints. Using the organic adhesive, Appu can cut any piece of sugarcane at joints and glue it to other sugarcane at its joint. enter image description here Now using this glue Appu thinks he can easily equalize the height of sugarcanes. But for this purpose he will have to buy lots and lots of "Organic Adhesive" which costs him Rs. R per joint he makes. He needs your help to determine how much money he will require to equalize all sugarcanes using the "organic adhesive", if you think Appu can still not equalize them all print "-1".

INPUT FORMAT:

Line 1: The number of sugarcanes, N and cost per join operation made,R[Integer] (1 <= N<= 1,000, 0<=R<=1000). Lines 2..1+N: Each line contains the number of joints in a single sugarcane (an integer in the range 0...1000).

OUTPUT FORMAT:

Line 1: The minimum amount of money Appu needs to spend in order to equalize heights of all the sugarcanes. If he cannot equalize the heights no matter what he does,print -1.

NOTE:

  1. Appu can cut any sugarcane at any joint.
  2. Appu cannot throw any sugarcane,nor any piece of it.
  3. If sugarcane has J joints and length of each piece or unit in sugarcane is L, then the height of sugarcane is (J+1)*L, so in simple words we have to make every sugarcane have same height, which means it must have same number of joints.
  4. Appu must have N sugarcanes of equal height after all cutting and joining operations

HINT When there are three sugarcanes of height 10,30 and 50 . Appu can cut the last sugarcane of height 50(30+20) into 2 sugarcanes of height 20 and 30 , and then he will use adhesive to join the smaller one with the first sugarcane of height 10 which will make it (10+20)30 as well. So he will have to use organic adhesive only once here

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

We have 3 sugarcanes of respective heights 3,2 and 4

to equalize them we will cut the sugarcane with height 4 and make it of height 3 and then we will use "organic adhesive" to join the spare sugarcane to the sugarcane with height 2, this way we can get 3 sugarcanes of height 3 each

Since we used "organic adhesive" only once, the cost will be Re. 1 /- only

Editor Image

?