기초마법학

GIST는 리버럴 아츠 칼리지 모델을 바탕으로 학부생에게 수준 높은 인문학과 사회학 교양 과목을 제공하고 있다.

2024년, GIST는 교양 과목으로 마법학을 새로 개설했다. GIST 캠퍼스에는 $N$개의 마법원이 있으며, 각 마법원은 좌표평면 위의 한 점으로 표현된다. 마법원은 마나의 세기와 색깔을 가진다. 마나의 세기는 양수이고, 색깔은 $1$부터 $K$까지의 정수로 나타낸다. 기초마법학 수업에서 마법진 그리기를 배우고 있는 해원이는 다음 조건을 만족하도록 마법진을 그려야 한다.

• 마법진은 직사각형이며, 각 변은 $x$축 또는 $y$축 중 하나에 평행하다.
• 직사각형의 네 꼭짓점 중 $x$좌표와 $y$좌표가 동시에 최소인 점은 $(0, 0)$이다.
• 마법진은 모든 색깔의 마법원을 포함해서는 안 된다. 마법원이 마법진의 둘레 또는 내부에 있으면 마법진이 그 마법원을 포함하는 것이다.

마법진의 힘은 직사각형의 내부 또는 네 변 위에 있는 모든 마법원의 마나 세기의 합이다. 마법진 안에 마법원이 하나도 없으면 마법진의 힘은 $0$이다. 마법진의 힘이 최대가 되도록 하라.

첫째 줄에 마법원의 개수 $N$과 마법원 색깔의 종류 수 $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 150000$, $2 \le K \le \min\{N, 10000\}$)

둘째 줄부터 $N$개의 줄에 걸쳐 네 정수 $x_i$, $y_i$, $p_i$, $c_i$가 공백으로 구분되어 주어진다. ($1 \le x_i, y_i \le 10^8$, $1 \le p_i \le 1000$, $1 \le c_i \le K$) 이는 $i$번째 마법원이 좌표 $(x_i, y_i)$에 있고, 마나의 세기가 $p_i$이며, 색깔이 $c_i$라는 뜻이다.

$1$ 이상 $K$ 이하의 모든 정수 $j$에 대하여, $j$번째 색깔을 가진 마법원이 적어도 하나 존재한다.

$x$좌표와 $y$좌표가 모두 같은 마법원이 두 개 이상 존재할 수 있으니 주의하시오.

주어진 조건을 만족하며 그릴 수 있는 마법진 힘의 최댓값을 출력한다.