#Alguns testes para o problema

Input
3 5 6 1
1 2 3
Output
2

4 40 50 10
10 20 30 25
Output
2

5 25 35 10
10 10 20 10 20
Output
6

Input
4 15 60 10
10 20 30 25
Output
6

Input
10 626451 11471247 246428
369649 684428 303821 287098 422756 301599 720377 177567 515216 750602
Output
914

Input
15 1415849 15540979 356865
8352 960238 276753 259695 712845 945369 60023 920446 181269 392011 318488 857649 30681 740872 115749
Output
31485

Input
15 4789415 23152928 233992
502422 273992 449428 947379 700461 681985 857134 243310 478052 77769 936151 642380 464695 281772 964693
Output
10875

Input
10 159699 10967276 3542
998862 999751 995306 992648 992661 991407 997503 998809 999740 997669
Output
942

Input
15 1 1000000000 1
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
Output
32752