## COCI '06 Regional #3 Firefly

View as PDF

Points: 10
Time limit: 0.6s
Python 2.0s
Memory limit: 32M
Python 128M

Problem type

A Japanese firefly has flown into a cave full of obstacles: stalagmites (rising from the floor) and stalactites (hanging from the ceiling). The cave is units long (where is even) and units high. The first obstacle is a stalagmite after which stalactites and stalagmites alternate.

Here is an example cave units long and units high (the image corresponds to the second example):

The Japanese firefly is not the type that would fly around the obstacle, instead it will choose a single height and ram from one end of the cave to the other destroying all obstacles in its path with its mighty kung-fu moves.

In the previous example, choosing the level from the ground has the firefly destroying eight obstacles:

This is not the best choice because the firefly will end up less tired if it chooses either level one or five, as that would require destroying only seven obstacles.

You are given the length and height of the cave and the sizes of all obstacles.

Write a program that determines the minimum number of obstacles the firefly needs to destroy to reach the end of the cave, and on how many distinct levels it can achieve that number.

#### Input Specification

The first line contains two integers and , , , the length and height of the cave. will always be even.

The next lines contain the sizes of the obstacles, one per line. All sizes are positive integers less than .

#### Output Specification

Output two integers separated by a single space on a single line. The first number is the minimum number of obstacles the firefly has to destroy and the second is the number of levels on which that can be achieved.

#### Sample Input 1

6 7
1
5
3
3
5
1

#### Sample Output 1

2 3

#### Sample Input 2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

#### Sample Output 2

7 2