Samples

2 3 2
3 10
2 5 15

8

3 3 0
1 3 3
6 2 7

-1

1 1 1000000000000000000
1000000000000000000
1000000000000000000

2000000000000000000

8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4

14

Limitation

1s, 1024KiB for each test case.