DJ 공연

Doug James는 Graphland에서 활동하는 신예 DJ인데, 성공하기까지 힘든 시기를 보내고 있었다. 최신 EP Wiggly Waves가 플래티넘과 우라늄 인증을 모두 받은 역사상 첫 앨범이 되면서 상황이 바뀌었다. 인기가 높아진 Doug(DJ Polygon)은 대부분의 아티스트가 부러워할 고민을 안게 되었다. 쏟아지는 공연 제안 중 어떤 것을 수락할지 정해야 한다.

Graphland에는 $K$개의 장소(venue)가 있고, $R$개의 도로로 연결되어 있다. 장소는 1번부터 $K$번까지 번호가 붙어 있다. Doug의 집은 1번 장소이며, 그는 시각 $t = 0$에 떠나거나 공연할 준비가 되어 있다.

Doug에게는 $G$개의 공연 제안이 들어와 있다. $i$번째 공연은 $V_i$번 장소에서 시간 구간 $[S_i, E_i)$ 동안 열리고(시작 시각 포함, 종료 시각 제외), $M_i$ 크립토센트를 준다. Doug은 동시에 여러 공연을 할 수 없고, 장소 사이를 이동하는 중에는 공연을 수락할 수 없다.

명성과 쏟아지는 공연 요청에 정신이 없는 Doug은 가능한 한 많은 돈을 벌 수 있도록 도움을 원한다.

첫 줄에 세 정수 $G$, $K$, $R$이 주어진다. 각각 공연 수, 장소 수, 도로 수이다. 이 값들은 $1 \leq G \leq 200000$, $1 \leq K \leq 100$, $0 \leq R \leq \min(4000, K(K-1)/2)$를 만족한다.

이어지는 $R$개의 줄에는 세 정수 $A_i$, $B_i$, $T_i$가 주어지며, $i$번째 (양방향) 도로를 나타낸다. 이 도로는 장소 $A_i$와 $B_i$를 잇고, 어느 방향으로 이동하든 $T_i$의 시간이 걸린다. $1 \leq A_i, B_i \leq K$, $A_i \neq B_i$, $1 \leq T_i \leq 1000000$을 만족한다. 두 장소 사이에는 도로가 최대 하나만 있다.

이어지는 $G$개의 줄에는 네 정수 $V_i$, $S_i$, $E_i$, $M_i$가 주어진다. $i$번째 공연은 장소 $V_i$에서 시각 $S_i$부터 $E_i$ 전까지 열리며 $M_i$ 크립토센트를 지급한다. 이 값들은 $0 \leq S_i < E_i \leq 1000000000$, $1 \leq M_i \leq 1000000$을 만족한다.

Doug이 공연을 골라 벌 수 있는 크립토센트의 최댓값을 정수 하나로 출력한다.

첫 번째 예제에서 장소 $1$에는 공연이 두 개, 장소 $2$에는 공연이 하나 있다. Doug은 장소 $1$에서 두 공연을 모두 하면 11 크립토센트를 받지만, 처음 10 시간 단위를 들여 장소 $2$로 이동해 그 공연을 하면 33 크립토센트를 받는다. Doug은 후자를 선택한다.

두 번째 예제에서는 Doug이 장소 $1$에 머물면서 두 공연을 모두 해서 70 크립토센트를 버는 것이 가장 많다.