Limousinen

I Taipei har IOI satt igång med ett intensivt schema av föreläsningar, lekar, förberedelser, matpauser, sömnpauser och tävlingar. Men arrangörerna har lämnat en timme fri för alla att göra vad de vill. Detta är ett problem som lagledarna inte alls förberett de tävlande på. Förvirring och kaos uppstår i de tävlandes hjärnor, och när fritidstimmen är slut så är de $N$ tävlande utspridda vid olika korsningar i storstaden och har inte en aning om hur de ska hitta tillbaka. Lyckligtvis hade tävlingsledningen installerat ett chip i varje tävlandes väska som gör att de kan se exakt vid vilken gatukorsning som varje vilsen tävlande befinner sig.

Limousinföraren Simon har fått i uppdrag att plocka upp de tävlande och köra dem, en i taget, till tävlingsarenan. Han vill naturligtvis undsätta dem i en ordning som gör att han hinner skjutsa tillbaka så många som möjligt innan nästa föreläsning börjar (vilket sker om $T$ minuter). Taipei kan modelleras som ett oändligt regelbundet rutnät där heltalskoordinater är korsningar och det finns lodräta och horisontella vägar. Det tar exakt 1 minut att köra från en korsning till en närliggande korsning.

Simon börjar vid tävlingsarenan på adressen $(0, 0)$, kör till den första personen och hämtar upp den och kör sedan hem personen till arenan. Därefter kör han till nästa person, o.s.v. Han fortsätter så tills tiden tar slut, och han kan alltså bara skjutsa en i taget. Om han väljer ordningen han hämtar upp de tävlande i optimalt, hur många hinner han hämta upp och skjutsa tillbaka inom $T$ minuter?

Indata

På första raden i indata står två heltal $1 \leq N \leq 100\, 000$ och $1 \leq T \leq 10^9$, antalet tävlande som ska plockas upp respektive hur lång tid Simon har på sig. Sedan följer $N$ rader (en rad per tävlande). Varje rad består av två heltal $-10^8 \leq x, y \leq 10^8$, $x$- och $y$-koordinater för personens nuvarande position.

Utdata

Skriv ut hur många tävlande som Simon hinner köra hem innan tiden är slut, givet att han väljer ordningen optimalt.

Exempel

I det första exempelfallet har Simon 5 minuter på sig, och det finns tre tävlande att hämta upp. Att hämta den första tävlande tar 4 minuter, att hämta den andra tar 6 minuter, och att hämta den trejde tar 4 minuter (om han åker optimalt). Eftersom han bara har 5 minuter på sig så hinner han då bara hämta en person.

I det andra exempeltestfallet hinner inte Simon hämta någon alls.

I det tredje exempeltestfallet hinner Simon precis hämta en person, personen som befinner sig vid $(-100, 0)$.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För 20 poäng gäller att $N \leq 10$ och att $-1\, 000 \leq x,y \leq 1\, 000$ för alla koordinater $(x,y)$.

• För ytterligare 30 poäng gäller att $N \leq 1\, 000$ och att $-10^6 \leq x,y \leq 10^6$ för alla koordinater $(x,y)$.

3 5
1 1
2 1
2 0

1

2 1
1 0
0 1

0

2 200
-100 0
231 -53

1