Codeforces Round 128 (Div. 2) |
---|
Закончено |
Валера приехал в Японию и купил много роботов для своих исследований. Он уже в аэропорте, до вылета осталось совсем немного, поэтому Валере срочно нужно доставить всех роботов до багажного отделения.
Роботы самоходные, и некоторые из них даже имеют отсеки для перевозки других роботов. Точнее, про i-го робота известно ci — количество роботов, которое он может перевезти. При этом, каждый из ci перевозимых роботов может дополнительно перевозить других роботов.
Однако для того, чтобы роботы поехали, в них нужно залить топливо, поэтому Валера потратил все свои последние деньги и купил S литров топлива. Он узнал, что каждый робот имеет ограничение на преодолеваемое расстояние. Таким образом, у i-го робота, помимо характеристики ci, имеются две характеристики fi и li — количество топлива (в литрах), необходимое i-ому роботу для движения, и максимальное расстояние, которое может проехать робот.
Ввиду ограниченного количества времени и топлива, Валера хочет перевезти в багажное отделение максимально возможное количество роботов. Он действует следующим образом.
До багажного отделения нужно проехать 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
Название |
---|