Sample 1

Input

3 10

3
1 3 6
4 7 9
8 10 3

3
1 3 5
4 7 10
8 10 1

4
1 3 2
4 8 2
9 9 6
10 10 3

Output

25

Limitation

1s, 64MiB for each test case.