OCC '19 B5 - Gold

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type

Modo's parents have a fortune of X gold bars in their possession. Each gold bar is worth Y dollars. Modo currently has Z dollars and has N sisters/brothers. Modo's parents are planning to give their fortune away to their children. They will first count the number of children that want the fortune, and divide the gold such that each child that wants the gold will get \lfloor\frac{X}{\large\text{number of children}}\rfloor gold bars. Initially, every child wants the gold, but Modo can buy out the i-th sister/brother for X_i amount of dollars. Modo can only use the amount of money she currently has to buy her sisters/brother out. Help Modo find out which siblings she should buy out to obtain the most amount of money after her parents distribute the gold fortune.

Input Specification

The first line will contain X, Y, Z, and N, the number of gold bars, the value of each gold bar, the amount of money Modo has, and the number of siblings Modo has.

The next line will contain N integers, representing X_i, the amount of money it costs to buy out the i-th child.

Output Specification

Output the maximum amount of money Modo can obtain after her parents distribute the gold.


1 \le X, Y, Z, N, X_i \le 10^5

Sample Input 1

6 1 4 2
3 1

Sample Output 1


Explanation 1

By buying out the second child, there will only be two children that want the fortune. Modo will receive 3 gold bars. Each gold bar sells for 1 dollar, so she will have 3 dollars from gold bars at the end. She spends 1 dollar buying the child out, so she has 6 dollars at the end.


There are no comments at the moment.