5
3 100 1
10000 1 7
25 1 12
15 5 504
50000 1000000 75