양조장을 어디에 지을까?

금주(Abstinence) 섬 주민들은 무알코올 맥주를 무척 좋아한다. 지금까지는 폴란드에서 수입해 왔지만, 올해 이 섬의 한 도시가 양조장을 짓기로 했다. 섬의 모든 도시는 해안에 있고, 해안을 따라 섬을 한 바퀴 도는 하나의 고속도로로 연결되어 있다. 즉 도시들은 하나의 원형 고리 위에 놓여 있다. 투자자는 각 도시가 하루에 필요로 하는 맥주 탱크 수(수요)와 도시 사이의 거리를 모두 조사했다. 맥주 한 탱크를 1마일 옮기는 데 드는 비용은 1탈러이다. 하루 운송 비용이란 양조장에서 각 도시로 필요한 만큼의 맥주 탱크를 옮기는 데 드는 전체 비용이며, 각 도시로는 고리에서 더 짧은 쪽 방향으로 운송한다. 이 비용은 양조장의 위치에 따라 달라지고, 투자자는 그 비용을 가장 작게 만드는 도시를 고르려고 한다.

다음을 수행하는 프로그램을 작성하라.

• 도시의 수, 도시 사이의 거리, 각 도시의 하루 맥주 수요를 읽는다.
• 최소 하루 운송 비용을 계산한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 도시의 수를 나타내는 정수 $n$이 주어진다 ($5 \le n \le 10\,000$). 도시는 고속도로를 따라 번호가 매겨져 있어 이웃한 도시는 연속한 번호를 가지며, 도시 $1$과 도시 $n$도 서로 이웃이다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 공백 하나로 구분된 두 음이 아닌 정수 $z_i$와 $d_i$가 주어진다. $z_i$는 도시 $i$의 하루 맥주 수요이고, $d_i$는 도시 $i$에서 고속도로를 따라 다음 도시까지의 거리(마일)이다. 고속도로 전체 길이는 $1\,000\,000$마일을 넘지 않는다. 각 도시의 맥주 수요는 $1\,000$탱크를 넘지 않는다.

첫째 줄에 최소 하루 운송 비용을 나타내는 정수 하나를 출력한다.