Nosaukums
Gardie dzērieni (gardie)
Laika limits
0.10s
Atmiņas limits
32.0 MB
Grūtība
70%

Definīcija

Jēkabs ir izlēmis uzsākt biznesu - garšīgo dzērienu ražotne. Viņam ir dažādi ļoti lielu tilpumu šķidrumi un viņš vēlas tos sajaukt, lai sajauktais dzēriens būtu pēc iespējas garšīgāks. Šķidrumi ir dažādos tilpumos un ar dažādām garšīguma pakāpēm. Diemžēl tilpumi ir tik lieli, ka Jēkabs nespēj ieliet daļu no šķidruma, tādēļ šķidrumu var tikai ieliet vai neieliet. Uzdevums ir aprēķināt, kurus dzērienus ielejot fiksēta tilpuma traukā var iegūt lielāko dzēriena garšīgumu.


Ievaddatu raksturojums

Pirmajā rindā tiek dots šķidrumu skaits 1 <= N <= 20 un jaucamā trauka tilpums 1 <= M <= 2 * 10 ^ 9. Katrā nākamajā rindā tiek doti 2 skaitļi a un b.

1 <= a <= 10^9 ir šķidruma tilpums.

1 <= b <= 10^9 ir šķidruma garšīgums.


Izvaddatu raksturojums

Rezultātā ir jāizvada šķidruma mazākais tilpums un lielākais garšīgums. Katrā nākamajā rindā ir jāizvada šķidruma kārtas numurs augošā secībā, kurš tiek ieliets traukā. Šķidrumus sāk skaitīt ar 1. Ja ir iespējams izvēlēties vairākus šķidrumus, lai iegūtu lielāko garšīgumu ar mazāko tilpumu, tad jāizvēlas tie trauki, kas ir vis vairāk pa labi jeb to numuriem jāveido mazākā augošā virkne.


Paraugdati

Stdin
3 10
7 10
4 6
4 5
Stdout
8 11
2
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.