Լևոնը և փքաբլիթները
Լևոնը շատ է սիրում փքաբլիթներ և գնացել է խանութ դրանց ետևից։ Խանութում գործում է 1+1=3 ակցիան։ Այսինքն 3 փքաբլիթ գնելու դեպքում, նրանցից ամենաքիչ արժեցողը տրվում է անվճար։ Օրինակ 1000, 1000 և 1000 դրամ արժեցող փքաբլիթներ գնելու համար Լևոնը պետք է վճարի 2000 դրամ, իսկ 1000, 2000 և 3000 դրամ արժեցող փքաբլիթներ գնելու համար Լևոնը պետք է վճարի 5000 դրամ։ Խանութում կա n փքաբլիթ։ i֊րդ փքաբլիթը արժի d[i] դրամ և ունի v[i] քաղցրություն։ Լևոնը քաղցրի սիրահար է, բայց չի սիրում չարաշահել, այդ պատճառով որոշել է գնել ուղիղ 3 փքաբլիթ։ Լևոնը ունի p դրամ և ցանկանում է գնել առավելագույն գումարային քաղցրություն ունեցող 3 փքաբլիթները, որոնք նա կարող է գնել իր ունեցած գումարով։
Պահանջվում է գրել ծրագիր, որը կօգնի Լևոնին պարզել ամենաշատը ինչքան գումարային քաղցրությամբ փքաբլիթներ կարող է նա գնել։
Մուտք
Առաջին տողում տրված են
n և p (n թիվ դասավորված ըստ չնվազման, որոնցից i-րդը ցույց է տալիս i-րդ փքաբլիթի գինը (i-րդ փքաբլիթի քաղցրությունը (Ելք
Ելքի միակ տողում պետք է տպել 1 թիվ ՝ Խնդրի պատասխանը։ Եթե Լևոնը չի կարող գնել ոչ մի 3 փքաբլիթ պետք է արտածել -1։
Սահմանափակումներ
- Թեստերի առաջին խմբի համար
1 ≤ n ≤ 500։
- Թեստերի երկրորդ խմբի համար
1 ≤ n ≤ 5000։
- Թեստերի առաջին խմբի համար
1 ≤ n ≤ 200 000։
- Թեստերի առաջին խմբի համար
1 ≤ n ≤ 1 000 000։
Օրինակներ
Մուտք | Ելք |
5 7000
1000 2000 3000 4000 5000
12 1 3 100 101 | 115 |
Աղբյուրը. Մարզային 2018
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB