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

 © acm.mipt DevGroupThe page was generated in 210ms