Problem G
Restaurant Bribes

Several participants in programming competitions end up
founding startup companies. Two of them created Eeet, a social
restaurant rating system. Each member of Eeet can rate a
restaurant with an integer score from
Two other past contestants have opened a restaurant, The
Smelly Fish, but they are bewildered as to why nobody is dining
at their establishment. Through experimentation they found out
that each person is willing to come once to the restaurant (for
some inexplicable reason no customer ever returns) and spend
However, they did not get any ratings yet, and all the fresh
produce they bought risks going past its prime. Hence they
selected some people to bribe so that they will leave them a
rating in Eeet. For each person, we know that they will give
The Smelly Fish a rating according to the function
Your task is to maximize the profit the restaurant makes, i.e., the income from customers minus the money spent on bribes.
Input
The first line contains three integers
Each of the next
Each of the next
Output
Output one line with the maximum profit the restaurant can
make. Answers with an absolute or relative precision up to
Sample Input 1 | Sample Output 1 |
---|---|
10 1 1 1 2 1 3 |
276 |