Sample 1

Input

5 100
8 2001 5
4 9 8
3 74 4
111 4
79 8
6 3
5 8
23 4

Output

10449

Limitation

1s, 64MiB for each test case.