Fan migration

Time limit1sMemory limit256 MB

Summary

Assign every family to a house inside its own supporter block so the total compensation paid to families moving into cheaper houses is minimal.

Level: Medium5 of 10
Topics: Graph
Solved: No attempts yet

Problem

Fans of two football teams, MC and MF, live in the town of M. The houses of the town stand along a single street and are numbered $1$ through $N$ . One family lives in each house.

The mayor is tired of the fights between the two sets of fans, so he has issued an edict that sends them to opposite ends of the street. The $K$ families who support MC must all move into houses $1$ through $K$ , and the $M$ families who support MF must all move into houses $N - M + 1$ through $N$ . Every family that supports neither team moves into a house numbered $K + 1$ through $N - M$ . Inside a block you may decide freely which family takes which house.

The mayor's assistants draw up a migration plan that meets those requirements. Every house has a price. A family that moves into a house cheaper than the one it used to live in receives compensation equal to the full price of its original house. A family that moves into a house of equal or higher price receives nothing. No family moves more than once.

Write a program that finds the smallest possible total compensation.

Input

The first line contains $N$ , the number of houses in the town. ( $2 \le N \le 300$ )

Each of the next $N$ lines contains two integers, describing house $1$ through house $N$ in order. The first integer is the price of the house. The second integer tells which team the family living there supports: $0$ for neither team, $1$ for MC and $2$ for MF. At least one family in the town supports each of the two teams. Prices are positive integers no greater than $1000$ .

Output

Print the smallest possible total compensation.

Hint

The first sample can be solved this way. The family in house $3$ moves to house $2$ and receives $3$ , the family in house $2$ moves to house $1$ and receives $2$ , and the family in house $1$ moves to house $3$ and receives nothing.

The second sample can be solved this way. The families in houses $1$ and $4$ swap houses and neither is compensated, and the family in house $3$ swaps with the family in house $5$ for a compensation of $6$ .

Examples6

Example 1
Input
```
3
1 2
2 1
3 0
```
Expected output
```
5
```
Example 2
Input
```
6
5 0
3 1
6 2
5 1
2 1
1 2
```
Expected output
```
6
```
Example 3
Input
```
2
4 1
9 2
```
Expected output
```
0
```
Example 4
Input
```
2
5 2
7 1
```
Expected output
```
7
```

Example 5

Input

Expected output

Example 6
Input
```
5
10 2
20 1
30 1
40 2
50 2
```
Expected output
```
30
```