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.

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.

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.