| Time Limit: | 1000ms |
Memory Limit: | 64000KiB |
| Accepted: | 0 |
Submitted: | 0 |
Diving
BOI 2000 Day 1 Problem 3
Diving
Each year there are diving courses in Ohrid. Different tasks are performed during the courses.
One of them is to dive from one side of the rock through an underwater passage to the other
side of the rock. The whole group of N students has only one oxygen bottle. No more then two
persons can use the same oxygen bottle at same time. Each diver has its own speed of diving,
so when two students dive together they dive with speed of the slower one (one with longer
diving time). There are M pairs of students that dislike each other and cannot dive together.
Task
Find one schedule to move the group of students from one side of the rock to the other side in minimal time.
Limitations
- N<=6000 is positive integer and is the number of students in the group.
- Each student is denoted by 1,2,...,N.
- M<=6000 is positive integer and is the number of student pairs that cannot dive together.
- ti is positive integer denoting the time required for the i-th student to move from one side of the rock to the other side.
- The oxygen bottle can only be moved from one side of the rock to the other side by diving. The oxygen bottle has unlimited capacity.
- There is always at least one solution in the test data.
- Time limit: 1 sec.
Input
The first line of the input consists of two integers N and M. In each of the next N lines there is
one integer ti. In each of the next M lines there are two integers representing a student pair that
cannot dive together.
Output
The first line of the output contains one integer, the minimal time required for moving all the students.
The next lines of the output file are reflecting one possible schedule of moves with minimal time. Each
line represents one move in the schedule. It consists of one or two integers denoting the student(s) who
dive with the oxygen bottle from one side of the rock to the other side.
Sample Input
4 2
1
2
1
2
3 4
2 3
Sample Output
6
3 1
1
4 2
3
3 1
SubmitStatistics |
