소 줄 세우기

농장에 존재하는 모든 서로 다른 품종을 각각 최소 한 마리씩 포함하는 사진 한 장을 찍으려고 한다.

$N$마리의 소가 직선 위 여러 위치에 서 있다. 각 소는 정수 위치($x$ 좌표)와 정수 품종 번호로 표현된다. 사진은 직선 위에서 연속된 구간에 속한 소들을 담으며, 그 비용은 사진의 크기, 즉 구간에 포함된 소들의 $x$ 좌표 중 최댓값과 최솟값의 차이와 같다.

농장에 존재하는 모든 서로 다른 품종을 각각 최소 한 마리씩 포함하는 사진의 최소 비용을 구하라.

• 첫째 줄: 소의 수 $N$ ($1 \le N \le 50{,}000$).
• 둘째 줄부터 $N+1$번째 줄까지: 각 줄에 한 마리 소의 $x$ 좌표와 품종 번호가 공백으로 구분되어 주어진다. 두 값 모두 $1{,}000{,}000{,}000$ 이하의 양의 정수이다.

• 모든 서로 다른 품종 번호를 각각 최소 한 마리씩 포함하는 사진의 최소 비용을 한 줄에 출력한다.

예를 들어 소가 $6$마리이고 위치가 각각 $25, 26, 15, 22, 20, 30$, 품종 번호가 각각 $7, 1, 1, 3, 1, 1$이라고 하자. 서로 다른 품종은 $1$, $3$, $7$이다. $x = 22$부터 $x = 26$까지의 구간은 크기가 $4$이고 세 품종을 모두 포함하며, 이것이 가능한 최소 비용이다.