29251번 - Вёлунд 다국어

По одной из версий <<Песни о Вёлунде>>, Вёланд женился на лебединой деве Хервёр Чудесной, которая родила ему сына Хейме, а затем покинула его, оставив ему свое кольцо в качестве напоминания о себе. Однако, согласно той же версии Вёланд выковал также несколько дубликатов этого кольца. Оставив неотвеченным вопрос о цели этого действия, рассмотрим более внимательно сам этот процесс.

Известно, что у Вёланда было ровно $m$ кузниц, $n$ кузнецов и $k$ дней на то, чтобы ковать эти кольца. При этом, каждый кузнец был готов работать только несколько (возможно, все или ноль) дней с номерами не меньшими, чем $l_i$, и не большими, чем $r_i$. Один кузнец успевал выковать за день работы ровно одно кольцо и требовал за день своей работы $c_i$ золотых монет. При этом, естественно, он занимал в этот день одну из кузниц, в которой в этот день не мог работать никто, кроме него.

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

Первая строка входного файла содержит три целых числа $n$, $m$ и $k$ ($1 \le m \le 100{\,}000, 1 \le n \le 200{\,}000$, $1 \le k \le 10^8$) --- количество кузнецов, кузниц и дней соответственно. Следующие $n$ строк содержат описания кузнецов.

Каждая строка с описанием кузнеца содержит три числа $l_i$, $r_i$ и $c_i$ ($1 \le l_i \le r_i \le k$, $1 \le c_i \le 10^4$) --- номер первого и последнего из дней, в которые этот кузнец готов работать, и требуемое им количество монет за один день работы.

Выведите два числа, разделенные пробелом --- количество колец, которые удастся заполучить Вёланду, и минимальное количество монет, которые ему потребуется на это потратить.

В приведенном примере первый кузнец будет работать все пять дней, второй --- только в первый и в четвертый день, а третий --- только во второй и в третий.