Input
3 5 3
5 9 1
Output
10
Input
5 10 3
1 2 3 4 5
Output
25