Virtuoso

Capba dreams of one day being a virtuoso trombone soloist... but for now, he must practice his boring exercises, which involve playing N (1 ≤ N ≤ 100000) notes, one after another. A trombone has seven slide positions, numbered closest to furthest from 1 to 7. The i^th note can be played in M_i (1 ≤ M_i ≤ 7) different slide positions.

Since he wants to save his energy for more interesting things, he wants to get through the exercise with as little effort as possible. Most importantly, this means minimizing the total distance that the slide moves. If two consecutive notes are played in positions x and y, then the slide moves a distance of |x-y|.

However, if there are multiple ways to play the exercise which minimize the movement of the slide, Capba wants the one which will minimize the number of times the slide must change direction — another important aspect which can reduce the amount of effort. Between two consecutive notes, with the first played in slide position x and the second in position y, the slide is either is moving in (x > y), stationary (x = y), or moving out (x < y).

Given the above criteria, your job is to find a way to play all of the notes in order that minimizes the effort required, and output the total distance travelled by the slide as well as the number of times it changes direction.

Input Format

Line 1: N

Next N lines: M_i, followed by M_i integers, denoting the slide positions in which note i can be played.

Output Format

Output two space-separated integers: the total distance travelled by the slide, followed by the number of direction changes, for the best solution.

Sample Input

8
2 1 6
2 3 6
2 1 4
2 3 6
2 1 5
2 2 6
1 4
2 6 1

Explanation

Twinkle, twinkle, little star (with repeated notes omitted).

Note 1 can be played in either position 1 or 6, note 2 in position 3 or 6, etc.

Notice that the slide positions can be given in any order.

Sample Output

10 2

Explanation

The best option is to play the notes in positions 6, 6, 4, 3, 1, 2, 4, 6. The total distance travelled is 0+2+1+2+1+2+2=10, and there are changes of direction after notes 2 and 5.

Note that other solutions exist which yield a distance of 10, such as always using the furthest slide position — however, they require more changes of direction.

All Submissions
Best Solutions

Point Value: 15
Time Limit: 2.00s
Memory Limit: 1024M
Added: Feb 22, 2011
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)