С окраины в центр города каждое утро по одному маршруту едут в трамвае \textbf{n }человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от \textbf{1} до \textbf{p}\textit{.} Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение \textit{суммарного удовлетворения} пассажиров. Для каждого \textbf{i}-го пассажира он оценил две величины - \textbf{a_i} и \textbf{b_i}. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется \textbf{a_i}, если же он стоит, то прибавляется \textbf{b_i}. Всего в трамвае \textbf{m }сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них \textbf{a_i} < \textbf{b_i}). Напишите программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого \textbf{i}-го пассажира известны величины \textbf{a_i} и \textbf{b_i}, а также номера остановок, на которых он садится и выходит из трамвая. \InputFile Первая строка содержит три целых числа \textbf{n}, \textbf{m} и \textbf{p} (\textbf{1} ≤ \textbf{n}, \textbf{m}, \textbf{p} ≤ \textbf{100 000}; \textbf{2} ≤ \textbf{p}) - число пассажиров, число сидячих мест и число остановок на маршруте соответственно. Каждая из следующих \textbf{n }строк содержит информацию об очередном пассажире в виде четырех целых чисел \textbf{a_i}, \textbf{b_i},\textbf{c_i}, \textbf{d_i}:, где первые два числа определяют вклад в параметр счастья, третье -- номер остановки, на которой пассажир садится в трамвай, и последнее -- номер остановки, на которой он выходит из трамвая (-\textbf{10^\{6 \}}≤ \textbf{a_i}, \textbf{b_\{i \}}≤ \textbf{10^6}; \textbf{1 }≤ \textbf{c_\{i \}}< \textbf{d_\{i \}}≤ \textbf{p}). \OutputFile Вывести максимальное суммарное удовлетворение, которого могут добиться пассажиры. \textbf{Комментарий к примеру} Максимальное суммарное удовлетворение достигается следующим образом: \begin{itemize} \item На первой остановке входят и садятся второй и третий пассажиры; \item На второй остановке входят первый и четвертый пассажиры, второй уступает место первому; \item На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места; \item На четвертой остановке выходят первый и третий пассажиры. \end{itemize}