Apart from plush toys, Imp is a huge fan of little yellow birds!

To summon birds, Imp needs strong magic. There are *n* trees in a row on an alley in a park, there is a nest on each of the trees. In the *i*-th nest there are *c*<sub class="lower-index">*i*</sub> birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him *cost*<sub class="lower-index">*i*</sub> points of mana. However, for each bird summoned, Imp increases his mana capacity by *B* points. Imp summons birds one by one, he can summon any number from 0 to *c*<sub class="lower-index">*i*</sub> birds from the *i*-th nest. 

Initially Imp stands under the first tree and has *W* points of mana, and his mana capacity equals *W* as well. He can only go forward, and each time he moves from a tree to the next one, he restores *X* points of mana (but it can't exceed his current mana capacity). Moving only forward, what is the maximum number of birds Imp can summon?
The first line contains four integers *n*, *W*, *B*, *X* (1 ≤ *n* ≤ 10<sup class="upper-index">3</sup>, 0 ≤ *W*, *B*, *X* ≤ 10<sup class="upper-index">9</sup>) — the number of trees, the initial points of mana, the number of points the mana capacity increases after a bird is summoned, and the number of points restored when Imp moves from a tree to the next one.

The second line contains *n* integers *c*<sub class="lower-index">1</sub>, *c*<sub class="lower-index">2</sub>, ..., *c*<sub class="lower-index">*n*</sub> (0 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>) — where *c*<sub class="lower-index">*i*</sub> is the number of birds living in the *i*-th nest. It is guaranteed that <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/74f3aaeca88b9721fe0f0b8ea082852e882209b2.png" style="max-width: 100.0%;max-height: 100.0%;"/>.

The third line contains *n* integers *cost*<sub class="lower-index">1</sub>, *cost*<sub class="lower-index">2</sub>, ..., *cost*<sub class="lower-index">*n*</sub> (0 ≤ *cost*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where *cost*<sub class="lower-index">*i*</sub> is the mana cost to summon a bird from the *i*-th nest.
In the first sample base amount of Imp's mana is equal to 12 (with maximum capacity also equal to 12). After he summons two birds from the first nest, he loses 8 mana points, although his maximum capacity will not increase (since *B* = 0). After this step his mana will be 4 of 12; during the move you will replenish 4 mana points, and hence own 8 mana out of 12 possible. Now it's optimal to take 4 birds from the second nest and spend 8 mana. The final answer will be — 6.

In the second sample the base amount of mana is equal to 1000. The right choice will be to simply pick all birds from the last nest. Note that Imp's mana doesn't restore while moving because it's initially full.
2 12 0 4
3 4
4 2
6
4 1000 10 35
1 2 4 5
1000 500 250 200
5
2 10 7 11
2 10
6 1
11
5 1 4 6
3 4 6 5 1
3 0 10 2 9
10
75 262 870 596
22 13 37 6 15 25 5 1 2 13 6 3 14 7 8 15 6 15 10 3 1 21 33 2 7 14 17 7 4 9 16 29 31 4 31 16 3 11 13 38 3 14 8 18 9 3 1 10 1 5 10 16 7 5 33 9 24 9 8 13 3 31 8 18 33 17 22 15 34 22 14 23 9 11 1
15 988 494 954 185 43 341 392 828 364 464 33 443 279 410 559 648 522 221 630 446 910 720 680 299 949 898 528 344 530 33 705 562 718 378 603 752 729 874 835 271 809 687 485 383 203 211 967 937 641 222 519 30 437 573 94 818 740 711 628 631 699 803 289 804 722 986 917 286 358 564 740 280 625 104
221
1 1000000000 1000000000 1000000000
10000
1000000000
1
11 182265379 943880823 541186655
118 395 182 912 3055 1198 972 499 1295 423 951
919515674 183547374 713185799 495395101 460570056 865323757 856004539 172194086 29017055 573281401 94884106
30
30 813763087 667301398 788083179
358 1 942 255 371 86 22 313 62 220 227 301 164 238 30 18 26 517 1904 293 110 1171 709 412 221 27 355 386 180 81
364514724 369447241 943009487 777239405 675813054 769495455 824525249 132802164 98954464 131625205 59567398 4498864 777027802 875631890 510915516 4505995 568141671 175640086 253104977 173981164 846365879 8456432 819645904 478042655 137080723 401949614 630869423 140199951 566654245 49531216
1648
29 248541711 775857221 991640811
456 358 735 868 213 24 583 174 381 1357 63 180 903 180 106 56 166 479 434 171 111 200 499 110 16 23 371 525 258
510246598 566510289 914900360 823548934 762398202 571897078 102256870 717967541 568392967 330484503 755710752 232910352 371570614 781299711 733550623 337438470 36696592 158396947 254877244 719491526 148294199 754511298 655210216 895287270 535726298 235308442 905006463 142116705 96440782
313
17 839860324 388827729 364896640
417 2 8 930 648 3105 434 435 1 1450 58 50 277 646 221 274 1044
416664151 309840428 823560106 653486427 281743349 81844030 406321182 683147664 445891025 323452426 204464623 21209374 112902821 403197845 977337836 263883864 161229864
95
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, w, b, x = map(int, input().split())
c = list(map(int, input().split()))
cost = list(map(int, input().split()))
dp0 = [w]
s = 0
inf = pow(10, 15) + 1
for i, u in zip(c, cost):
    s += i
    dp = [-1] * (s + 1)
    v = b - u
    q, k = [], 0
    for j in range(s + 1):
        if j < len(dp0):
            dp0[j] = min(dp0[j] + x, w + j * b)
            y = dp0[j]
            while len(q) ^ k and dp0[q[-1]] - u * (j - q[-1]) <= y:
                q.pop()
            q.append(j)
        while len(q) ^ k and q[k] + i < j:
            k += 1
        if len(q) ^ k:
            dp[j] = min(dp0[q[k]] - u * (j - q[k]), w + j * b)
        if dp[j] < 0:
            dp[j] = -inf
    dp0 = dp
    while dp0[-1] < 0:
        dp0.pop()
        s -= 1
ans = len(dp) - 1
print(ans)