eolymp
Problems

The vouchers

The vouchers

Time limit 1 second
Memory limit 128 MiB

The tour operator did not sell n (n < 15) vouchers to mountain-ski resort because of the great frost. The terms of vouchers validity is already come. To reduce the losses, it was decided from the February 1, that all the vouchers for which remained d[k] (d[k]30) days, to sell for minimal cost – for c[k] (c[k]100) UAH for a day only for that days, which remained from the sale day (k = 1..n).

What is the largest amount of income can get the travel company selling these vouchers, if one voucher can be sold only in one day?

Input data

The first line contains the number of vouchers n. Each of the next n lines contains two numbers - the number of days d[k] left and the cost of each day c[k].

Output data

The maximum amount of income.

Examples

Input example #10
4
2 37
3 45
1 46
4 30
Output example #10
232