Problem B
Expensive Board Games
John frequently borrows board games from his local board game library. Each game has two attributes:
-
a due date, and
-
an overdue fee charged per day after the due date; that is, if John returns the game on or before the day it is due, he will not have to pay this fee.
The library enforces a strict policy: a person may return at most one board game per day, and a person cannot return any games on the day they borrow a game. At the beginning of the month, John borrows several games. Because he is busy with schoolwork, he wants to schedule the return of these games in an order that minimizes the total overdue fee.
Given the list of games, their due dates, and their daily overdue fees, determine the minimum total overdue fee John must pay.
Input
The first line of input contains a single integer $n$ ($1 \leq n \leq 500$), the number of games John borrows.
Each of the next $n$ lines contains two integers:
-
$d$ ($1 \leq d \leq n$) — the number of days until the $i_{th}$ game is due,
-
$p$ ($1 \leq p \leq 10^5$) — the overdue fee per day for the $i_{th}$ game.
Output
Output a single integer $c$, the minimum total overdue fee that John must pay.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 10 2 20 3 30 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 10 1 20 1 30 |
40 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 10 1 10 1 10 |
30 |
