Az I/S. 14. feladat (2017. január)

I/S. 14. Meseországban rövid kirándulást teszünk, ahol az úthálózat nagyon egyszerű: az \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle i\)-edik és az \(\displaystyle (i+1)\)-edik helyszín között \(\displaystyle U[i]\) percig (pozitív egész), az \(\displaystyle N\)-edik és az első helyszín között pedig az út \(\displaystyle U[N]\) 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 \(\displaystyle M\) percig tart. (A helyszínek megtekintésének idejét nem vesszük figyelembe.)

A standard bemenet első sora tartalmazza a helyszínek \(\displaystyle N\) számát és a percek \(\displaystyle M\) számát (egész számok). A második sor \(\displaystyle N\) egész számot tartalmaz, az \(\displaystyle i\)-edik szám \(\displaystyle E[i]\) értéke az \(\displaystyle i\)-edik helyszín érdekessége. A harmadik sor \(\displaystyle N\) számot tartalmaz, az \(\displaystyle i\)-edik szám \(\displaystyle U[i]\) é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 \(\displaystyle N\le 100\). További két tesztesetben \(\displaystyle N\le 10\,000\).

Korlátok: \(\displaystyle 1\le N\le 10^6\), \(\displaystyle 1\le M,E[i],U[i]\le 10^9\).

Magyarázat: a második helyszínről indulva a harmadik helyszínen át a negyedik helyszínen befejezve \(\displaystyle 10+15+12=37\) az érdekességek összege, az idő pedig \(\displaystyle 10+20=30\), ami belefér a rendelkezésre álló 30 percbe.

(10 pont)

A beküldési határidő 2017. február 10-én LEJÁRT.

Statisztika:

16 dolgozat érkezett.
10 pontot kapott:	Busa 423 Máté, Csertán András, Gáspár Attila, Janzer Orsolya Lili, Kiss Gergely, Molnár Bálint, Németh 123 Balázs, Noszály Áron.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2017. januári informatika feladatai