Input
3 3 3 100
1 1 1
Output
10
Input
3 6 5 1000000007
1 2 3
Output
0
Input
3 5 6 11
1 2 1
Output
0