Maximum Painting Value

You are given multiple test cases. Each test case describes a sequence of rooms in a building and the available paintings in each room. In every room, there are several paintings; each painting has a dominant color (represented by an integer from 1 to R) and a corresponding value. The objective is to select one painting per room such that the sum of the values is maximized, with the added restriction that two consecutive rooms cannot have paintings of the same dominant color.

Formally, for a test case you are given:

• An integer N representing the number of rooms.
• An integer R representing the number of possible dominant colors.
• For each room i (1 ≤ i ≤ N), an integer M indicates the number of available paintings, followed by 2M integers. Each pair of integers represents the dominant color c (1-indexed) and the value v of a painting.

The constraint is that if the painting chosen in room i has dominant color c, then the painting chosen in room i+1 must have a dominant color \( c' \) such that \( c' \neq c \). The goal is to maximize the sum of the values of the chosen paintings.

Note: If a room has no available paintings (i.e. M = 0), then its contribution is 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \( T \), the number of test cases.
• For each test case:
• The first line contains two space-separated integers \( N \) and \( R \), where \( N \) is the number of rooms and \( R \) is the number of possible dominant colors.
• Then follow \( N \) lines. Each line begins with an integer \( M \) (the number of paintings in that room) followed by \( 2M \) space-separated integers. Each pair describes a painting: the first integer is its dominant color (1-indexed) and the second is its value.

outputFormat

For each test case, output a single integer on a new line representing the maximum total value that can be achieved by selecting one painting per room under the given constraint.

## sample

3
3 3
2 1 100 2 200
3 1 300 2 400 3 500
2 2 150 3 250
2 2
2 1 100 2 200
2 1 150 2 250
1 3
3 1 100 2 200 3 300

850
350
300

</p>