You are living in Singapore, a country with N bus stops numbered 1 to N inclusive, where from bus stop #i you can only go to bus stop #(i+1). For each i where 1 ≤ i

You are currently in bus stop #1 and you want to go to bus stop #N. You want to spent least amount of money possible to reach bus stop #N without taking the same bus twice (taking two bus with the same number). Note that this means you are also not allowed to take the same bus from bus stop #i to bus stop #(i+2). In other words, you must get off the bus at every bus stop.

Input

The first line will consist of an integer N (2 ≤ N ≤ 7) indicating the number of bus stops.

The next N-1 blocks of input represents the bus options. The i-th block of input represents the bus options from bus stop #i to bus stop #(i+1). Each block of input has the following format:
The first line consist of an integer K (1 ≤ K ≤ 7), which is the number of buses available.
The next K lines consist of two integers B and P (1 ≤ B, P ≤ 1000) separated by a space, describes the bus option. It means this bus option has the bus number equal to B, and costs $P.

Output

If it is possible for you to go from bus stop #1 to #N without taking the same bus twice, print the minimum amount of money that you must spent in dollar. Otherwise, you must print “CAN MEH?” (without quote).

Explanation for Examples

In the first example, the minimum total cost will be achieved if you take 188 from bus stop #1 to bus stop #2, take 96 from bus stop #2 to bus stop #3, and take 95 from bus stop #3 to bus stop #4. You will spend (200 + 1 + 1000) = 1201 dollars.

In the second example, it is obviously impossible for you to go to bus stop #N since from bus stop #1 to #2 and from bus stop #3 to #4, the available bus is only 95. Therefore, you will not be able to reach but stop #N without taking bus 95 twice.

Example

Input:
4
2
95 100
188 200
3
95 1
96 1
97 100
1
95 1000

Output:
1201

Input:
4
1
95 100
3
95 1
96 1
97 100
1
95 1000

Output:
CAN MEH?