트램

도시 외곽에서 중심가로 매일 아침 한 노선의 트램을 타고 N명이 이동한다. 오랫동안 함께 다니면서 그들은 서로를 꽤 잘 알게 되었다. 아무도 서운하지 않도록, 그들은 누가 노선의 어느 정류장 사이에서 앉아야 하고 누가 서 있어야 하는지를 정하기로 했다. 모든 정류장은 1부터 P까지 번호가 매겨져 있다.

승객 중 한 명은 수학적 모델링 이론에 능통했다. 그는 승객들의 총 만족도 값을 생각해 보자고 제안했다. 각 i번째 승객에 대해 그는 두 값 ai와 bi를 평가했다. 정류장 사이를 한 번 이동하는 동안 승객이 앉아 있으면 총 만족도에 ai가 더해지고, 서 있으면 bi가 더해진다.

트램에는 M개의 좌석이 있다. 승객은 어느 정류장에서든 즉시 일어나고 앉을 수 있다. 또한 일부 승객은 트램에 빈 좌석이 있어도 서서 가는 것을 선호한다(그들에게는 ai < bi).

각 i번째 승객의 값 ai와 bi, 그리고 그가 트램에 타고 내리는 정류장 번호가 주어졌을 때, 도달할 수 있는 최대 총 만족도 값을 계산하는 프로그램을 작성해야 한다.

입력 파일의 첫째 줄에는 공백으로 구분된 세 정수 N, M, P가 주어진다. 이는 각각 승객 수, 좌석 수, 노선의 정류장 수이다(1 ≤ N, M, P ≤ 100 000; 2 ≤ P).

다음 N개 줄에는 각 승객에 대한 정보가 네 정수 ai, bi, ci, di의 형태로 주어진다. 처음 두 수는 행복 매개변수에 대한 기여도를 나타내고, 세 번째는 승객이 트램에 타는 정류장 번호, 마지막은 그가 트램에서 내리는 정류장 번호이다(−10^6 ≤ ai, bi ≤ 10^6; 1 ≤ ci < di ≤ P).

출력 파일에는 승객들이 달성할 수 있는 최대 총 만족도를 나타내는 정수 하나를 출력해야 한다.

최대 총 만족도는 다음과 같이 달성된다.

• 첫 번째 정류장에서 두 번째와 세 번째 승객이 타서 앉는다;
• 두 번째 정류장에서 첫 번째와 네 번째 승객이 타고, 두 번째 승객이 첫 번째 승객에게 자리를 양보한다;
• 세 번째 정류장에서 첫 번째와 세 번째 승객이 일어나 내리고, 두 번째와 네 번째 승객이 그 자리에 앉는다;
• 네 번째 정류장에서 첫 번째와 세 번째 승객이 내린다.