bursa

Bogdan are $S$ lei şi vrea să îi investească în acţiuni la SIF Moldova. Acum este foarte simplu, pentru că Bursa Română are un site pe care poţi vinde sau cumpăra acţiuni. Mai mult decât atât, pe site sunt afişate şi previziunile experţilor pentru următoarele $n$ zile. Mai exact, pentru fiecare zi $i$, se cunoaşte preţul de cumpărare $c_i$ (preţul cu care ar putea să cumpere Bogdan o acţiune în ziua $i$), precum şi preţul de vânzare $v_i$ (suma pe care Bogdan ar putea să o obţină vânzând o acţiune în ziua $i$).
Fiindcă este începător, Bogdan intenţionează să facă cel mult două tranzacţii în decursul acestor $n$ zile: într-o zi să cumpere acţiuni, iar în altă zi să vândă toate acţiunile cumpărate.

Cerinţă

Determinaţi suma maximă pe care o poate avea Bogdan, efectuând eficient cele două tranzacţii.

Date de intrare

Fişierul de intrare bursa.in conţine pe prima linie numere naturale $n$ şi $S$, cu semnificaţia din enunţ. Pe a două linie se află $n$ numere naturale $c_1 \ c_2 \dots c_n$ (sumele cu care poate fi cumpărată o acţiune în fiecare dintre cele $n$ zile). Pe a treia linie se află $n$ numere naturale $v_1 \ v_2 \dots v_n$ (sumele cu care poate fi vândută o acţiune în fiecare dintre cele $n$ zile). Numerele aflate pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire bursa.out va conţine pe prima linie numărul natural $SMAX$, reprezentând suma maximă pe care o are Bogdan după $n$ zile. Pe cea de a doua linie vor fi scrise două numere naturale $D_1$ şi $D_2$ separate prin spaţiu, cu semnificaţia că în ziua $D_1$ Bogdan cumpără acţiuni, iar în ziua $D_2$ le vinde $(1 \leq D_1 < D_2 \leq n)$. Dacă Bogdan nu cumpără/vinde acţiuni pe cea de a doua linie se vor afişa valorile $-1 \ -1$.

Restricţii

• $1 \leq n \leq 500$
• $1 \leq S \leq 1\ 000\ 000$
• $1 \leq v_i, c_i \leq 1\ 000$, pentru $1 \leq i \leq n$
• Dacă există mai multe soluţii, afişaţi soluţia cu $D1$ minim. Dacă există mai multe soluţii cu $D1$ minim, afişaţi soluţia cu $D2$ minim.
• Pentru determinarea corectă a sumei maxime se acordă $60\%$ din punctaj; punctajul integral se acordă pentru rezolvarea ambelor cerinţe.

Exemplul 1

bursa.in

5 1000
2 3 1 4 3
1 2 1 2 3

bursa.out

3000
3 5

Explicație

Bogdan are $1000$ lei. In cea de a treia zi cumpără $1000$ de acţiuni cu preţul de $1$ leu. În cea de a cincea zi vinde cele $1000$ de acţiuni cu $3$ lei bucata, obţinând suma maximă de $3000$ lei.

Exemplul 2

bursa.in

3 1000
4 3 2
3 2 1

bursa.out

1000
-1 -1

Explicație

Bogdan are $1000$ lei. El nu cumpără/vinde acţiuni. Rămâne cu $1000$ lei.