| Codeforces Round 419 (Div. 1) |
|---|
| Закончено |
На пути домой Карен решила зайти в супермаркет за продуктами.
Ей нужно купить много продуктов, но, так как она еще учится, ее бюджет ограничен. Она может потратить не более b долларов.
В супермаркете есть n товаров. Товар номер i может быть куплен за ci долларов. Конечно, каждый товар может быть куплен только один раз.
Супермаркет хочет расширяться, поэтому Карен получила n купонов. Если Карен купит i-й товар, то она может использовать i-й купон для того, чтобы уменьшить цену этого товара на di. Конечно, купон не может быть использован без покупки соответствующего товара.
Однако, на использование купонов накладывается ограничение. Для всех i ≥ 2, чтобы использовать купон номер i, Карен должна использовать также купон номер xi (для использования которого может понадобиться использовать другие купоны, чтобы выполнить условие).
Карен хочет узнать, сколько максимум товаров она может купить, не превысив своего бюджета b?
Первая строка содержит два целых числа n и b (1 ≤ n ≤ 5000, 1 ≤ b ≤ 109) — число товаров в магазине и количество денег у Карен, соответственно.
Следующие n строк описывают товары. А именно:
- Строка номер i начинается с двух целых чисел ci и di (1 ≤ di < ci ≤ 109) — цены i-го товара и скидка при использовании купона для i-го товара, соответственно.
- Если i ≥ 2, то далее следует еще одно целое число xi (1 ≤ xi < i), означающее, что перед тем как будет использован этот купон, необходимо использовать купон номер xi.
Выведите одно целое число: количество товаров, которые Карен может купить, не превысив бюджет.
6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5
4
5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4
5
В первом примере Карен может купить следующие 4 товара:
- Используя первый купон для покупки первого товара за 10 - 9 = 1 доллар.
- Используя третий купон для покупки третьего товара за 12 - 2 = 10 долларов.
- Используя четвертый купон для покупки четвертого товара за 20 - 18 = 2 доллара.
- Купив шестой товар за 2 доллара.
Суммарная стоимость равна 15, что не превышает бюджета. Заметьте, например, что она не может использовать купон на шестой товар, так как тогда она должна будет использовать пятый купон и купить пятый товар, что она не сделала.
Во втором примере у Карен достаточно денег, чтобы использовать все купоны для покупки всех товаров.
