E. Перевозки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Валера приехал в Японию и купил много роботов для своих исследований. Он уже в аэропорте, до вылета осталось совсем немного, поэтому Валере срочно нужно доставить всех роботов до багажного отделения.

Роботы самоходные, и некоторые из них даже имеют отсеки для перевозки других роботов. Точнее, про i-го робота известно ci — количество роботов, которое он может перевезти. При этом, каждый из ci перевозимых роботов может дополнительно перевозить других роботов.

Однако для того, чтобы роботы поехали, в них нужно залить топливо, поэтому Валера потратил все свои последние деньги и купил S литров топлива. Он узнал, что каждый робот имеет ограничение на преодолеваемое расстояние. Таким образом, у i-го робота, помимо характеристики ci, имеются две характеристики fi и li — количество топлива (в литрах), необходимое i-ому роботу для движения, и максимальное расстояние, которое может проехать робот.

Ввиду ограниченного количества времени и топлива, Валера хочет перевезти в багажное отделение максимально возможное количество роботов. Он действует следующим образом.

  • Сначала Валера выбирает некоторых роботов, которые самостоятельно поедут в багажное отделение. При этом суммарное количество топлива, необходимое для движения всех этих роботов, не должно превосходить S.
  • Затем Валера рассаживает роботов по отсекам так, чтобы было перевезено как можно больше роботов. Обратите внимание, что роботы, которые не движутся сами, но находятся на движущихся роботах непосредственно или через других роботов, также могут быть нагружены.
  • После этого, все выбранные и рассаженные роботы, вместе с Валерой, отправятся к багажному отделению, а остальные будут утрачены.

До багажного отделения нужно проехать d метров. Поэтому те роботы, которые будут перевозить остальных, должны иметь показатель li не меньше, чем d. Во время движения Валера не может останавливаться и менять каким-либо образом расположение роботов.

Помогите Валере узнать, какое максимальное количество роботов удастся увезти домой, и какое при этом минимальное количество топлива придется затратить, ведь оставшееся топливо очень пригодится Валере при исследованиях.

Входные данные

В первой строке через пробел заданы три целых числа n, d, S (1 ≤ n ≤ 105, 1 ≤ d, S ≤ 109). Первое число означает количество роботов, второе — расстояние до багажного отделения, третье — количество топлива, имеющееся у Валеры.

В следующих n строках заданы описания роботов. В i-ой строке через пробел заданы три целых числа ci, fi, li (0 ≤ ci, fi, li ≤ 109) — характеристики i-го робота. Первое число — количество роботов, которое i-ый робот может перевезти, второе — количество топлива, необходимое i-ому роботу для движения, третье — максимальное расстояние, которое может проехать i-ый робот.

Выходные данные

Выведите через пробел два целых числа — максимальное количество роботов, которое Валера сможет довезти до багажного отделения, и минимальное количество топлива, которое при этом он затратит. Если Валере не удастся довезти до багажного отделения ни одного робота, то выведите два нуля.

Примеры
Входные данные
3 10 10
0 12 10
1 6 10
0 1 1
Выходные данные
2 6
Входные данные
2 7 10
3 12 10
5 16 8
Выходные данные
0 0
Входные данные
4 8 10
0 12 3
1 1 0
0 3 11
1 6 9
Выходные данные
4 9