Problem D
Pickle Clicker

För ungefär ett halvår sedan släpptes succéspelet Pickle Clicker. Efter att ha lagt otaliga timmar på spelet har Rasmus bestämt sig för att ta saker och ting till nästa nivå: han tänker speedrunna spelet.

Pickle Clicker går ut på att man samlar ihop så mycket som möjligt av valutan pickles. Målet i en speedrun är att köpa Megapickeln så fort som möjligt, som kostar $T$ pickles. I spelet finns även $N$ olika typer av byggnader. De olika typerna är numrerade från $1$ till $N$, där den $i$:te typen producerar $p_ i$ pickles per sekund och kostar $c_ i$ pickles att bygga.

I början äger du en byggnad av typ $1$. Varje sekund sker följande:

1. Varje byggnad du äger producerar pickles. En byggnad av typ $i$ producerar $p_ i$ pickles.

2. Därefter har du alternativet att köpa en byggnad eller köpa Megapickeln. En byggnad av typ $i$ kostar $c_ i$ pickles att bygga, och du måste ha råd med den för att få köpa den. Du får maximalt köpa en byggnad per sekund, och det är tillåtet att ha flera byggnader av samma typ.

Hjälp Rasmus bestämma hur han ska spela spelet så att han kan köpa Megapickeln på så få sekunder som möjligt. Se exemplet nedan för att få en tydligare bild av reglerna.

Indata

Den första raden innehåller heltalen $N$ och $T$ ($1 \le N \le 6$, $1 \leq T \leq 10^5$), antalet byggnader och priset av Megapickeln.

Därefter följer $N$ rader. Den $i$:te av dessa rader innehåller heltalen $p_ i, c_ i$ ($1 \leq p_ i,c_ i \leq T$), produktionshastigheten och kostnaden av byggnad $i$.

Utdata

Skriv ut ett heltal, antalet sekunder det tar att vinna Pickle Clicker om man spelar optimalt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

2 100
3 3
50 10

5

1 100000
1 1000

6179