mese
At company DOT on planet CAMP n persons are employed, numbered from 1 la n. The big boss is preparing a party for all the employees. One or more employees will be seated at each table respecting the following rules:
- the sum of the ages of the employees seated at the same table must not exceed value S;
- any two people a and b,
seated at the same table, either know each other or there are k
persons from that same table x1,
x2, …, xk
so that a knows x1,
x1 knows x2,…
xk knows b.
The company being very large, every person only knows his direct supervisor and his direct subordinates. The hierarchy in the company is not contradictory, therefore there is no chain in form x1 is the boss of x2, x2 is the boss of x3,…, xk-1 is the boss of xk, xk is the boss ofx1.
Task
Write a program that determines the minimum number of tables required for the party.
Input Data
Line one of input file mese.in contains numbers n and S, separated by a space. The following n lines each contain two integers separated by a space; the first number on line i+1 represents i's direct boss and the second number represents i's age. There is a single line, corresponding to the big boss, in which the direct boss is 0.
Output Data
Output file mese.out will contain a single line with the minimum number of tables necessary for the party.
Restrictions
Example
|
mese.in |
mese.out |
Explanation |
|
6 10 |
3 |
A possible seating arrangement at the 3 tables: |
Time limit: 0.2 seconds/test
Total available memory: 5 Mb, of which 1 Mb for the stack.
prof. Nistor Mot
"N.Balcescu" National High School