Bản đồ mặt bẳng của một công trình xây dựng là một hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị (\(m,n \le 10^6\)), các hàng ô của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới và các cột ô của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên giao của hàng \(x\) và cột \(y\) được gọi là ô \((x,y)\).

Mùa mưa đến, người ta muốn tôn cao mặt bằng của công trình để tránh ngập úng bằng cách dùng \(k\) (\(k \le 10^6\)) chuyến xe ben chở đất đá bên ngoài đổ vào mặt bằng công trình. Chuyến xe thứ \(i\) đổ vào ô \((x_i,y_i)\) đúng \(a_i\) tấn đất đá (\(a_i\) là số nguyên, \(\forall i:1 \le i \le k\)). Tổng khối lượng đất đá được các chuyến xe ben đổ vào công trình là số nguyên không vượt quá \(10^{12}\) và chia hết cho \(m \times n\).

Tiếp theo, máy ủi được điều tới để san đều toàn bộ khối lượng đất đá này vào các ô. Chi phí để máy ủi chuyển mỗi tấn đất đá từ một ô sang một ô khác kề cạnh là \(1\) (chú ý là không được chuyển đất ra khỏi mặt bằng công trình).

Yêu cầu: Tìm cách điều khiển các máy ủi để san đều toàn bộ khối lượng đất đá vào các ô với chi phí ít nhất. Cho biết chi phí đó.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(m,n,k\).
• \(k\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(x_i,y_i,a_i\).

Output

• Một số nguyên duy nhất là chi phí san đều toàn bộ khối lượng đất đá vào các ô theo phương án tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m \le 2\).
• Subtask \(2\) (\(25\%\) số điểm): \(m,n \le 20\).
• Subtask \(3\) (\(25\%\) số điểm): \(m,n \le 2000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

3 3 4
1 1 4
1 1 5
3 1 3
3 2 6

18