축구팀 팬 이주

시간 제한1초메모리 제한256 MB

요약

각 가족을 자기 응원 구단의 구역 안에 배정해 싼 집으로 옮기는 가족에게 주는 보상금 총액을 최소화합니다.

난이도: 보통10점 중 5점
유형: 그래프
정답자: 아직 제출이 없습니다

문제

M 마을에는 축구팀 MC와 MF의 팬이 산다. 마을의 집은 하나의 거리를 따라 $1$ 번부터 $N$ 번까지 나란히 놓여 있고, 집마다 한 가족이 산다.

시장은 두 팀 팬 사이의 다툼에 지쳐서 팬을 거리 양 끝으로 갈라놓는 포고령을 내렸다. MC 팬 $K$ 가구는 모두 $1$ 번부터 $K$ 번까지의 집으로 옮겨야 하고, MF 팬 $M$ 가구는 모두 $N - M + 1$ 번부터 $N$ 번까지의 집으로 옮겨야 한다. 어느 팀의 팬도 아닌 나머지 가족은 $K + 1$ 번부터 $N - M$ 번까지의 집으로 옮긴다. 정해진 구간 안에서 어느 가족이 어느 집에 들어갈지는 자유롭게 정할 수 있다.

시장의 보좌관은 이 조건을 지키는 이주 계획을 세워야 한다. 집마다 가격이 정해져 있다. 원래 살던 집보다 가격이 낮은 집으로 옮기는 가족에게는 보상금을 주며, 금액은 그 가족이 원래 살던 집의 가격 전액이다. 가격이 같거나 더 높은 집으로 옮기는 가족에게는 보상금을 주지 않는다. 어떤 가족도 두 번 옮기지 않는다.

이주에 드는 보상금 총액의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 집 개수 $N$ 이 주어진다. ( $2 \le N \le 300$ )

다음 $N$ 개의 줄에는 $1$ 번 집부터 차례로 정수 두 개가 주어진다. 첫 번째 정수는 그 집의 가격이고, 두 번째 정수는 그 집에 사는 가족이 어느 팀의 팬인지를 나타낸다. $0$ 은 어느 팀의 팬도 아님, $1$ 은 MC 팬, $2$ 는 MF 팬을 뜻한다. 두 팀 각각의 팬이 마을에 적어도 한 가족씩 있다. 집의 가격은 $1000$ 이하의 자연수이다.

출력

이주에 드는 보상금 총액의 최솟값을 출력한다.

힌트

첫 번째 예제는 이렇게 풀 수 있다. $3$ 번 집의 가족이 $2$ 번 집으로 옮겨 보상금 $3$ 을 받고, $2$ 번 집의 가족이 $1$ 번 집으로 옮겨 보상금 $2$ 를 받으며, $1$ 번 집의 가족은 $3$ 번 집으로 옮겨 보상금을 받지 않는다.

두 번째 예제는 이렇게 풀 수 있다. $1$ 번 집과 $4$ 번 집의 가족이 서로 집을 바꾸면 보상금이 없고, $3$ 번 집의 가족과 $5$ 번 집의 가족이 서로 집을 바꾸면서 보상금 $6$ 이 나간다.

예제6

예제 1
입력
```
3
1 2
2 1
3 0
```
예상 출력
```
5
```
예제 2
입력
```
6
5 0
3 1
6 2
5 1
2 1
1 2
```
예상 출력
```
6
```
예제 3
입력
```
2
4 1
9 2
```
예상 출력
```
0
```
예제 4
입력
```
2
5 2
7 1
```
예상 출력
```
7
```

예제 5

입력

예상 출력

예제 6
입력
```
5
10 2
20 1
30 1
40 2
50 2
```
예상 출력
```
30
```