La firma DOT de pe planeta
CAMP lucreaza n persoane, numerotate
de la 1
la n. Seful cel mare pregateste o petrecere la care sa participe
toti angajatii. La fiecare masa se vor aseza unul sau mai multi angajati respectand
urmatoarele doua reguli:
- suma varstelor angajatilor asezati la aceeasi masa sa nu depaseasca valoarea
S;
- oricare doua persoane a si
b, persoane asezate la aceeasi
masa, fie se cunosc, fie exista k
persoane de la aceeasi masa x1,
x2, …, xk
astfel incat a cunoaste pe x1,
x1 cunoaste pe x2,…
xk cunoaste pe b.
Firma fiind foarte mare, fiecare se cunoaste doar cu seful sau direct si cu
subordonatii sai directi. Ierarhia din firma este necontradictorie, adica nu
exista un lant de forma x1
este seful lui x2,
x2 este seful lui
x3,…, xk-1
este seful lui xk,
xk este seful lui
x1.
Cerinta
Scrieti un program care
sa determine numarul minim de mese necesare pentru petrecere.
Date de intrare
Pe prima linie a fisierului
de intrare mese.in sunt scrise
numerele n si S,
separate printr-un spatiu. Pe urmatoarele n
linii sunt scrise cate doua numere intregi separate de cate un spatiu; primul
numar de pe linia i+1 reprezinta
seful direct al lui i, al doilea
numar reprezinta varsta lui i.
Exista o singura linie, corespunzatoare sefului cel mare, in care seful direct
este 0.
Date de iesire
Fisierul de iesire mese.out
va contine o singura linie pe care va fi scris numarul minim de mese necesare
pentru petrecere.
Restrictii
2 <= n <= 100 000
Varstele sunt numere
intregi din intervalul [1,
255].
S
este un numar natural <= 30000
Nici o varsta nu depaseste
valoarea S.
Exemplu
mese.in
mese.out
Explicatie
6 10
5 9
3 4
0 2
2 4
3 7
2 2
3
O posibila aranjare
la cele 3 mese: (3 5)
(2 4 6)
(1)