Pradipti is going to her hometown, Kolkata from her college. There are N stations (excluding the starting station) in this journey. She is at the starting station and initially she has no chocolate with her. She will travel from starting station to 1st station, then from 1st station to 2nd station and so on till Nth station. She is allowed to travel only when she has some non-negative number of chocolates with her at any point of time during the journey including starting and ending stations. When she reaches to (K+1)th station from the Kth station then she will get CK - CK+1 number of chocolates for free (if this value is negative then she will lose these number of chocolates). Price of one chocolate is P rupees. She can purchase any number of chocolates at any time. But she don’t want to spend too much. Can you help her in spending minimal amount of money in order to reach the destination i.e to the Nth station.
Test case #1 : She will purchase one chocolate at station 1 and one at station 2.
Test case #2 : She will purchase one chocolate at station 1 , one at station 2 and one at station 3.