## 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`integers, denoting the slide positions in which note

_{i}`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)

It's quiet in here...