Short on Fuel

Hyangbin, who had always dreamed of seeing the pyramids in person, signed up for a desert tour package. On the second day of the trip he arrived at the entrance of the desert and boarded the car used for the desert tour.

While he sat in the car waiting to depart, he found a desert tour guidebook. On the $R \times C$ map inside the guidebook, the locations of $N$ fuel depots and the amount of fuel stored at each depot were marked.

Hyangbin was a car enthusiast who had memorized the fuel efficiency of every car, and he knew that the car he was riding consumes $1$ unit of fuel for every $1$ unit of distance it travels. The car only drives in directions parallel to the $x$-axis or the $y$-axis of the map. For example, if the car moves from $\left(0,0\right)$ to $\left(i,j\right)$ along a shortest path, it consumes $i+j$ units of fuel.

The car currently has no fuel, so he plans to refuel at the gas station here before departing. Because the fuel sold at the gas station is very expensive, Hyangbin will put in as little fuel as possible here and refuel afterward at the fuel depots he visits along the way.

Hyangbin wants to see the pyramids as soon as possible, so he asked the driver not to drive in the direction away from the pyramids. In other words, the car moves only right or down.

There is no limit on the amount of fuel that can be put in at the gas station, and there is no fuel depot at the current location or at the location of the pyramids. Also, no location has two or more fuel depots.

Because each fuel depot has a different location and amount of stored fuel, the amount of fuel that must be put in at the start can differ depending on the order in which the fuel depots are visited. Find the minimum amount of fuel that must be put in at the gas station for Hyangbin to travel from the current location $\left(1,1\right)$ to the point $\left(R,C\right)$ where the pyramids are.

The first line gives the integers $R$ and $C$, the height and width of the map. ($2 \leq R, C \leq 3\ 000$)

The second line gives the integer $N$, the number of fuel depots marked on the map. ($0 \leq N \leq 1\ 000$)

Each of the next $N$ lines gives the integer coordinates $\left(r,c\right)$ of a fuel depot and the integer $f$, the amount of fuel stored there. ($1 \leq r \leq R$, $1 \leq c \leq C$, $0 \leq f \leq 100$)

Print the minimum amount of fuel that must be put in at the gas station for Hyangbin to travel from the current location $\left(1,1\right)$ to the point $\left(R,C\right)$ where the pyramids are.