Input

3 1
5 10 5
4 7 2
1 1 1
10

Output

18

Input

3 2
5 10 1
4 7 2
1 1 1
10 15

Output

19 27

Nguồn: 3D '1920