Cave Firefly

A firefly is trying to fly through a cave of length \(n\) units and height \(h\) units. Inside the cave, there are two kinds of obstacles:

• Stalagmites that grow from the floor upward.
• Stalactites that hang from the ceiling downward.

The obstacles are arranged along the cave in an alternating fashion. The first obstacle (at the leftmost end) is always a stalagmite, the second a stalactite, the third a stalagmite, and so on.

A stalagmite of height \(a\) occupies all levels from \(1\) to \(a\) (inclusive). A stalactite of length \(b\) occupies all levels from \(h - b + 1\) to \(h\) (inclusive). The firefly chooses a constant flight height \(x\) (where \(1 \le x \le h\)) and flies in a straight line through the cave. At each unit of distance, if an obstacle exists at height \(x\), the firefly collides with it.

Your task is to determine the minimum number of obstacles the firefly would have to destroy (i.e. the minimum number of collisions) and also count how many flight levels achieve that minimum collision count.

For example, consider a cave of length \(n = 14\) and height \(h = 5\) with obstacles given in order as follows:

1
3
4
2
2
4
3
4
3
3
3
2
3
3

If the firefly flies at level \(4\), it collides with 8 obstacles. However, flying at level \(1\) or \(5\) results in only 7 collisions, which is optimal. Hence, the answer would be 7 2 (7 collisions and 2 possible levels achieving this optimum).

inputFormat

The first line contains two integers \(n\) and \(h\) (where \(n\) is even), representing the length of the cave and its height, respectively. \(n\) lines follow. The \(i\)th obstacle is described by a single integer indicating its size:

• If \(i\) is odd, the obstacle is a stalagmite with the given height.
• If \(i\) is even, the obstacle is a stalactite with the given length.

Constraints: \(1 \le n \le 200000\), \(1 \le h \le 500000\). (Note: These constraints are for context; efficient solutions are required.)

outputFormat

Print two space‐separated integers: the minimum number of obstacles the firefly would collide with, and the number of levels at which this minimum is achieved.

sample

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

7 2