<PREV Problem:
NEXT>
Solved by 20 users: WsemirZ, Cheryl, wInuX, lutyj, tourist, dan, zloy_mipt, chenxiuwei, KZ, mazahaka, MIKseR, UdH-WiNGeR, defrager, RAVEman, topspin, fetetriste, EAA2008, Dest, LiuChenheng, JohnJones_001.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Time Management (Refactoring 2)

Time limit = 5 second(s)

See problem 132.

Now tasks have value. Your program should choose tasks with maximum total value (no need to maximaze number of tasks).

Input First line contains number of tasks N, 0 < N < 10001. Each of next N lines contains four numbers. First two integer numbers from [0, 2000000000] state for beginning and ending of time frame (those are represented in minutes from some fixed moment in time). Third number is 0 (task can be excluded) or 1 (task is mandatory). Fourth number is task value from [0, 10000]. Task's lengths are not less than 20 minutes.

Output First line should contain two integer numbers K and V — number of non-overlapping tasks and maximum total value.

Next K lines should contain description of K chosen tasks. In each line: identifier of a task and shift of that task (integer number from [-10,10]).

All important tasks should be chosen.

If it's not possible, output single line "NO SOLUTION".

Input#1
3
6 31 1 0
20 52 1 0
40 73 1 10000
Output#1
NO SOLUTION 
Input#2
5
0 21 1 0
1 22 1 0
11 32 0 765
41 62 1 872
42 63 1 12
Output#2
NO SOLUTION 
Input#3
7
56 98 0 10
30 66 0 21
1 30 0 3
37 58 1 1
6 38 0 4
40 62 1 29
62 85 0 43 
Output#3
4 77
4 -9
3 -8
5 10
6 10
Input#4
7
66 98 1 3
30 66 0 1
1 30 0 5
37 59 1 3
6 38 0 2
40 62 0 6
48 70 0 10000
Output#4
4 10011
2 2
3 -5
6 6
0 10


Author:
Sanekf
21 May 2008

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.162.181.75