Meseországban rövid kirándulást teszünk, ahol az úthálózat nagyon egyszerű: az $N$ érdekes helyszín mind egyetlen kör alakú út mentén helyezkedik el sorban. Kaptunk egy varázstérképet, amiről rögtön tudjuk, hogy melyik helyszín mennyire érdekes. A kirándulást bármelyik helyszínen elkezdhetjük, és bárhol befejezhetjük, viszont csak $M$ percünk van. A térképről tudjuk bármely két szomszédos helyszínről, hogy mennyi ideig tart az út (az $i$-edik és az $\left(i+1\right)$-edik helyszín között $U\left[i\right]$ percig (pozitív egész), az $N$-edik és az első helyszín között pedig az út $U\left[N\right]$ percig tart).
Írjunk programot, amely a térkép alapján megtervez egy maximális érdekességű kirándulást (az érdekesség a meglátogatott helyszínek érdekességének összege; minden helyszín legfeljebb egyszer számít), és amely maximum $M$ percig tart. (A helyszínek megtekintésének idejét nem vesszük figyelembe.)
A standard bemenet első sora tartalmazza a helyszínek $N$ számát és a percek $M$ számát (egész számok). A második sor $N$ egész számot tartalmaz, az $i$-edik szám $E\left[i\right]$ értéke az $i$-edik helyszín érdekessége. A harmadik sor $N$ számot tartalmaz, az $i$-edik szám $U\left[i\right]$ értéke. A standard kimenet első és egyetlen sorába írjuk ki a legérdekesebb út érdekességét.
Pontozás: Az első két tesztesetben $N\le 100$. További két tesztesetben $N\le 10000$.
Korlátok: $1\le N\le {10}^6$, $1\le M\mathrm{,}E\left[i\right]\mathrm{,}U\left[i\right]\le {10}^9$.