버스

어떤 도시의 도로는 체스판처럼 규칙적인 격자를 이룬다. 모든 도로는 남북 방향(NS 도로) 또는 동서 방향(WE 도로)으로 뻗어 있으며, 각 도로는 도시 전체를 가로지른다. 모든 NS 도로는 모든 WE 도로와 교차하고 그 반대도 마찬가지다. NS 도로는 가장 서쪽부터 $1$번부터 $n$번까지, WE 도로는 가장 남쪽부터 $1$번부터 $m$번까지 번호가 매겨져 있다. $i$번째 NS 도로와 $j$번째 WE 도로의 교차점을 순서쌍 $(i, j)$로 나타낸다($1 \le i \le n$, $1 \le j \le m$).

이 도시에는 교차점을 정류장으로 삼는 버스 노선이 하나 있다. 버스는 교차점 $(1, 1)$에서 출발하여 교차점 $(n, m)$에서 운행을 마치며, 동쪽 또는 북쪽 방향으로만 이동할 수 있다(즉 한 번 이동할 때마다 NS 도로 번호나 WE 도로 번호가 증가한다).

일부 교차점에는 승객이 버스를 기다리고 있다. 운전기사는 되도록 많은 승객을 태울 수 있는 경로를 고르려 한다(버스는 어떤 경로를 택하든 지나가는 모든 승객을 태울 만큼 충분히 넓다고 가정한다).

도로망의 정보와 각 교차점에서 기다리는 승객 수가 주어질 때, 버스가 태울 수 있는 승객 수의 최댓값을 출력하는 프로그램을 작성하라.

첫째 줄에 세 양의 정수 $n$, $m$, $k$가 주어진다. 각각 NS 도로의 수, WE 도로의 수, 그리고 승객이 기다리는 교차점의 수를 뜻한다($1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le k \le 10^5$).

이어지는 $k$개의 줄에는 각 교차점의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 공백으로 구분된 세 양의 정수 $x_i$, $y_i$, $p_i$가 있으며($1 \le x_i \le n$, $1 \le y_i \le m$, $1 \le p_i \le 10^6$), 이는 교차점 $(x_i, y_i)$에서 $p_i$명의 승객이 기다리고 있음을 뜻한다. 각 교차점은 입력에 최대 한 번만 등장한다. 기다리는 승객 수의 총합은 $10^9$을 넘지 않는다.

버스가 태울 수 있는 승객 수의 최댓값을 정수 하나로 한 줄에 출력한다.