И всё было бы хорошо, так нет же — министр промышленности Силантий возьми да и скажи, что отчего бы сметане подешеветь, ежели закваску у Берендея и покупаем. И пастеризаторы. И запчасти к ним. А упаковку у короля Сигизмунда. И хорошо, что министр экономики Калистрат начал про перспективы производства упаковки в царстве рассказывать, а то Силантий бы еще много чего перечислил.
Царь Пантелеймон заинтересовался, почему производство упаковки решили организовывать, а не, к примеру, пастеризаторов. Калистрат пояснил, что упаковка не только для сметаны годится. Так что начать решили с производства того продукта, который наибольшее влияние на другие оказывает. А пастеризаторы чуть позже производиться начнут — вот только упаковочный завод построим, так за другие возьмёмся.
Ведомство Калистрата определяет влияние следующим образом. Пусть для каждого продукта известно, какие продукты непосредственно требуются для его производства. Для каких-то из этих продуктов, в свою очередь, также известны те, что требуются для их производства (и т.д.) Также для каждого из продуктов известно, какая сумма потребуется на организацию его производства.
Назовём цепочкой последовательность продуктов, в которой каждый продукт (за исключением последнего) непосредственно используется для производства следующего. Мерой влияния некоторого продукта будем считать максимально возможную длину цепочки, начинающейся с этого продукта. Дело, однако, несколько осложняется тем, что на организацию производства из казны может быть выделена сумма, не превосходящая s. Поэтому придется выбирать наиболее влиятельный продукт в рамках этого бюджета.
Ваша задача — определить этот продукт.
В первой строке содержатся целые числа n и s (1 ≤ n ≤ 105, 1 ≤ s ≤ 109) — количество продуктов и сумма, которую можно потратить.
В каждой из следующих n строк содержится описание очередного продукта (считайте продукты занумерованными в порядке их появления во входном файле). Описание состоит из цены продукта, количества продуктов, которые непосредственно требуются для его производства, и их номеров.
Гарантируется, что если для производства продукта #j прямо или косвенно требуется продукт #k, то для производства продукта #k ни прямо, ни косвенно не требуется продукт #j. Гарантируется также, что общее количество чисел в строках не превосходит 3·105 и что стоимость организации производства по крайней мере одного продукта не превосходит s.
Выведите единственное число — номер продукта, который является наиболее влиятельным и при этом доступным для организации производства. Если таких продуктов несколько, выведите любой.
8 50
35 3 2 5 8
52 2 4 6
22 1 4
68 1 7
54 0
50 3 7 3 5
62 0
18 2 5 2
3
