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 ci (preţul cu care ar putea să cumpere Bogdan o acţiune în ziua i), precum şi preţul de vânzare vi (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 doua linie se află n numere naturale c1 c2 ... cn (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 v1 v2 ... vn (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 D1 şi D2 separate prin spaţiu, cu semnificaţia că în ziua D1 Bogdan cumpără acţiuni, iar în ziua D2 le vinde (1 ≤ D1 < D2 ≤ 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 ≤ n ≤ 500
• 1 ≤ S ≤ 1 000 000
• 1 ≤ vi , ci ≤ 1000, pentru 1 ≤ i ≤ 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.
Exemple
bursa.in
bursa.out
Explicaţii
5 1000
2 3 1 4 3
1 2 1 2 3
3000
3 5
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.
3 1000
4 3 2
3 2 1
1000
-1 -1
Bogdan are 1000 lei. El nu cumpără/vinde acţiuni. Rămâne cu 1000 lei.