Competitions

# 26-ЖДУ_2

# The vouchers

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

The first line contains the number of vouchers **n**. Each of the next **n** lines contains two numbers - the number of days `d`

left and the cost of each day _{k}`c`

._{k}

#### Output

The maximum amount of income.

Input example #10

4 2 37 3 45 1 46 4 30

Output example #10

232