A - リレー競技 (Relay) Editorial /

Time Limit: 1 sec / Memory Limit: 512 MiB

Score: 100 points

Problem Statement

There are N members in the track club of JOI High School, numbered from 1 to N. For the member i (1 \le i \le N), the time of the 100 m sprint is A_{i} msec, and the ability of controlling the baton is B_{i}.

The track club will participate in a national contest for the 300 m relay. Three members will run in the 300 m relay. Each member will run for 100 m. A runner will pass the baton to the next runner. Precisely, if the first runner is the member i (1 \le i \le N), the second runner is the member j (1 \le j \le N), and the third runner is the member k (1 \le k \le N), then the three members will run the relay in the following steps.

  1. The member i runs for 100 m with a baton. It takes A_{i} msec.
  2. The member i gives a baton to the member j. It takes \max(B_{i}, B_{j}) msec.
  3. The member j runs for 100 m with a baton. It takes A_{j} msec.
  4. The member j gives a baton to the member k. It takes \max(B_{j}, B_{k}) msec.
  5. The member k runs for 100 m with a baton. It takes A_{k} msec.

Therefore, the record for the 300 m relay is A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k} msec. Here \max(x, y) is the largest value of x and y. Since you are the coach of the track club, you want to choose three distinct members for the relay and decide the order of the runners so that the record becomes minimum.

Write a program which, given information of the N members of the track club, calculates the minimum possible record of the 300 m relay.

Input

Read the following data from the standard input. Given values are all integers.

N
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

Output

Write one line to the standard output. The output should contain an integer which is the minimum possible record of the 300 m relay counted by msec.

Constraints

  • 3 \le N \le 200\,000.
  • 1 \le A_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le B_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).

Subtasks

  1. (25 points) N \le 100.
  2. (33 points) N \le 3\,000.
  3. (10 points) A_{1} = A_{2} = \cdots = A_{N}.
  4. (32 points) No additional constraints.

Sample Input 1

4
1070 90
1080 70
1050 60
1020 100

Sample Output 1

3320

If the first runner is the member 4, the second runner is the member 3, and the third runner is the member 2, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 1020, 100, 1050, 70, 1080 msec, respectively. Thus, the record for the 300 m relay will be 1020 + 100 + 1050 + 70 + 1080 = 3320 msec. Since it is the minimum possible record, output 3320.

This sample input satisfies the constraints of Subtasks 1, 2, 4.

Sample Input 2

5
1000 28
1000 14
1000 21
1000 20
1000 14

Sample Output 2

3034

If the first runner is the member 2, the second runner is the member 5, and the third runner is the member 4, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 1000, 14, 1000, 20, 1000 msec, respectively. Thus, the record for the 300 m relay will be 1000 + 14 + 1000 + 20 + 1000 = 3034 msec. Since it is the minimum possible record, output 3034.

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3

Sample Output 3

13

If the first runner is the member 1, the second runner is the member 2, and the third runner is the member 9, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 3, 1, 4, 3, 2 msec, respectively. Thus, the record for the 300 m relay will be 3 + 1 + 4 + 3 + 2 = 13 msec. Since it is the minimum possible record, output 13.

This sample input satisfies the constraints of Subtasks 1, 2, 4.

配点 : 100 点

問題文

JOI 高校の陸上部には N 人の部員がおり,1 から N までの番号が付けられている.部員 i (1 \leqq i \leqq N) の 100\:\textrm{m} 走のタイムは A_{i} ミリ秒であり,バトンパスの速さは B_{i} である.

さて,この陸上部は 300\:\textrm{m} リレーの全国大会に出場することになった.300\:\textrm{m} リレーは,3 人の走者がバトンを渡しながら 100\:\textrm{m} ずつ走る競技である.具体的には,第 1 走者が部員 i (1 \leqq i \leqq N),第 2 走者が部員 j (1 \leqq j \leqq N),第 3 走者が部員 k (1 \leqq k \leqq N) であるとき,以下の手順で行われる.

  1. 部員 i がバトンを持って 100\:\textrm{m} 走る.これには A_{i} ミリ秒かかる.
  2. 部員 i から部員 j にバトンを渡す.これには \max(B_{i}, B_{j}) ミリ秒かかる.
  3. 部員 j がバトンを持って 100\:\textrm{m} 走る.これには A_{j} ミリ秒かかる.
  4. 部員 j から部員 k にバトンを渡す.これには \max(B_{j}, B_{k}) ミリ秒かかる.
  5. 部員 k がバトンを持って 100\:\textrm{m} 走る.これには A_{k} ミリ秒かかる.

すなわち,300\:\textrm{m} リレーの記録は A_{i} +\max(B_{i}, B_{j})+A_{j} +\max(B_{j}, B_{k})+A_{k} ミリ秒となる.ここで,\max(x, y) は x と y のうち小さくない方の数とする.あなたは陸上部の顧問であるため,この記録ができるだけ短くなるように 3 人の異なる部員を選び,その走順を決めなければならない.

陸上部の N 人の部員の情報が与えられたとき,300\:\textrm{m} リレーの記録として考えられる最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

出力

標準出力に,300\:\textrm{m} リレーの記録として考えられる最小値をミリ秒単位で表す整数を 1 行で出力せよ.

制約

  • 3 \leqq N \leqq 200\,000.
  • 1 \leqq A_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq B_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).

小課題

  1. (25 点) N \leqq 100.
  2. (33 点) N \leqq 3\,000.
  3. (10 点) A_{1} = A_{2} = \cdots = A_{N}.
  4. (32 点) 追加の制約はない.

入力例 1

4
1070 90
1080 70
1050 60
1020 100

出力例 1

3320

第 1 走者に部員 4,第 2 走者に部員 3,第 3 走者に部員 2 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 1020, 100, 1050, 70, 1080 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 1020 + 100 + 1050 + 70 + 1080 = 3320 ミリ秒となる.これより記録を短くすることはできないため,3320 を出力する.

この入力例は小課題 1, 2, 4 の制約を満たす.

入力例 2

5
1000 28
1000 14
1000 21
1000 20
1000 14

出力例 2

3034

第 1 走者に部員 2,第 2 走者に部員 5,第 3 走者に部員 4 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 1000, 14, 1000, 20, 1000 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 1000 + 14 + 1000 + 20 + 1000 = 3034 ミリ秒となる.これより記録を短くすることはできないため,3034 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3

出力例 3

13

第 1 走者に部員 1,第 2 走者に部員 2,第 3 走者に部員 9 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 3, 1, 4, 3, 2 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 3 + 1 + 4 + 3 + 2 = 13 ミリ秒となる.これより記録を短くすることはできないため,13 を出力する.

この入力例は小課題 1, 2, 4 の制約を満たす.


Source Name

JOIG 2021/2022 春合宿 Contest Day1 問題1