기초마법학

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

2024년, GIST는 교양으로 마법학 과목을 신설했다. GIST 부지 내에는 $N$개의 마법원이 있고, 각각의 마법원은 좌표평면 위 하나의 점으로 표현된다. 마법원들은 각각 마나의 세기와 색깔을 가진다. 마나의 세기는 양수이고, 색깔은 $1$과 $K$ 사이의 정수로 표현할 수 있다. 기초마법학 수업의 일환으로 마법진 그리기를 배우고 있는 해원이는 다음 조건을 만족시키며 마법진을 그려야 한다.

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

마법진의 힘은 직사각형의 내부 또는 네 변의 위에 있는 모든 마법원의 마나의 세기의 총합이다. 만약 마법진 내에 하나의 마법원도 포함되어 있지 않다면, 마법진의 힘은 $0$이다. 마법진의 힘을 최대화하시오.

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

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

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

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

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