전자 부품

면접 대비

시간 제한4초메모리 제한1024 MB

요약

부품 N종의 개수와 설치 시간이 주어질 때, 서로 다른 두 부품을 동시에 설치하는 방식으로 전체 설치 시간의 최솟값을 구합니다.

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

문제

Sara는 NCPC(Never Crashing Personal Computers)에서 여름 인턴을 하고 있다. 어느 날 사무실에 희귀한 생명체가 나타났는데, 바로 알고리즘 문제였다!

회사에는 전자 부품을 회로 기판에 배치하는 기계가 있다. 보통은 한 번에 부품 하나씩 배치한다. 최근 업데이트로 서로 다른 부품 두 개를 동시에 배치할 수 있게 되었다. 이때 배치 시간이 더 긴 부품이 전체 시간을 결정한다. 전체 배치 시간을 최소로 만드는 전략은 분명하지 않다. Sara는 이 전략을 찾는 알고리즘을 작성하기로 했다.

전자 부품은 $N$ 가지 종류가 있다. $i$ 번째 종류의 부품은 $f_i$ 개가 있고, 이 종류 부품 하나를 배치하는 데 $t_i$ 나노초가 걸린다. 목표는 여러 번의 작업으로 모든 부품을 배치하는 것이다. 한 번의 작업에서 기계는 종류 $i$ 와 종류 $j$ 의 부품을 하나씩 골라 동시에 배치할 수 있다. 단, $i \neq j$ 이다. 이 작업은 $\max(t_i, t_j)$ 나노초가 걸린다. 기계는 종류 $i$ 의 부품을 하나만 배치할 수도 있으며, 이때는 $t_i$ 나노초가 걸린다.

모든 부품을 배치하는 데 걸리는 최소 시간을 구하라.

입력

첫 번째 줄에 정수 $N$ ( $1 \leq N \leq 1000$ )이 주어진다.

이어지는 $N$ 개의 줄에는 각각 두 정수 $f_i$ 와 $t_i$ ( $1 \leq f_i \leq 10^4$ , $1 \leq t_i \leq 10^9$ )가 주어진다.

출력

모든 부품을 배치하는 데 걸리는 최소 시간을 정수 하나로 출력한다.

예제3

예제 1
입력
```
3
2 7
2 1
3 10
```
예상 출력
```
31
```
예제 2
입력
```
3
2 10
2 11
2 12
```
예상 출력
```
35
```
예제 3
입력
```
4
2 11
7 10
3 5
1 1
```
예상 출력
```
72
```