mese

В една компания работят n човека, номерирани от 1 до n. Шефът планира да организира банкет за всичките служители. На всяка маса на банкета трябва да седнат един или повече служители, съгласно следните правила:

 

- сумата от възрастите на служителите, седнали на една и съща маса не трябва да надминава стойността S;
- всеки двама служители
a и b, които са седнали на една и съща маса са такива, че или се познават, или могат да се намерят k служителя, седнали на същата маса: x1, x2, …, xk, такива че a познава x1, x1 познава x2,… , xk познава b.

Понеже компанията е много голяма, всеки служител познава само своя пряк началник и своите преки подчинени. Йерархията в компанията е непротиворечива, т.е. не съществува възможността: x1 да е началник на x2, x2 да е началник на x3,…, xk-1 да е началник на xk, xk да е началник на x1.

Задача

Напишете програма, която определя минималния брой на масите, които са необходими за банкета.

Вход

Първият ред на входния файл mese.in съдържа числата n и S, разделени с интервал. Всеки от следващите n реда съдържа две цели числа, разделени с интервал: първото число от (i+1)-вия ред показва номера на служителя, който е пряк шеф на служителя с номер i,  а второто число от същия ред показва възрастта на служителя с номер i. Измежду тези редове, има един единствен, съответстващ на шефа на компанията, при който на мястото на номера на неговия пряк началник е записано числото 0.

Изход

Изходният файл mese.out трябва да съдържа единствен ред с търсената минимална стойност.

Ограничения

  • 2 <= n <= 100 000
  • Възрастите са цели числа от интервала [1, 255].
  • S е положително цяло число  <= 30000
  • Никоя възраст не надминава стойността S.

Пример

mese.in

mese.out

Обяснение

6 10
5 9
3 4
0 2
2 4
3 7
2 2

3

Едно възможно разпределение на 3 маси е следното:
(3 5)
(2 4 6)
(1)

Време за работа на програмата: 0.2 seconds/test
Разрешена памет: 5 Mb, от които 1 Mb за стек.

prof. Nistor Mot
"N.Balcescu" National High School Brăila
Contact:emotz_ro@yahoo.co.uk

Превод на български: Емил Келеведжиев