Input
3 5 10 1 5
1 3 1
Output
12
2 5 2
Input
3 5 10 1 339
1 3 1
Output
35
5 5 5