Hide

Fastest Relay

/problems/codesprintla20.fastestrelay/file/statement/en/img-0001.jpg
Swimming Pool Lane 6 Empty. Photo by Pixabay

The UCLA Swim and Dive team wants to make the fastest medley relay they possibly can. A medley relay consists of 4 swimmers with one swimmer swimming each of the four strokes in alphabetical order: Backstroke, Breaststroke, Butterfly, and Freestyle. Exactly four swimmers must be on the relay since no one swimmer can swim two of the strokes in the same relay.

Input

The first line of input contains the number of swimmers on the team $n$ ($4 \le n \le 1\, 000$). The following $n$ lines consist of the times in each of the $4$ strokes of $n$ swimmers. Each line represents a swimmer, and contains 4 space-separated integers ($1 \le i \le 1000$) representing the swimmer’s time in seconds for backstroke, breaststroke, butterfly, and freestyle (in that order).

Output

Print a single integer corresponding to the fastest possible swim time in seconds.

Sample Input 1 Sample Output 1
4
9 1 3 8
10 4 5 5
8 4 3 10
10 9 4 2
16
Sample Input 2 Sample Output 2
5
5 7 9 2
9 7 2 4
10 3 3 7
9 2 1 1
5 10 7 1
10
Sample Input 3 Sample Output 3
6
5 3 4 7
4 7 8 2
1 9 6 10
6 10 3 8
7 2 10 5
7 3 9 7
8
CPU Time limit 1 second
Memory limit 1024 MB
Author
Elena Escalas
Source CodeSprintLA 2020 (UCLA ACM-ICPC)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in