Hộp bi của Bờm có dạng 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)\). Ban đầu hộp bi chưa có viên bi nào.

Đầu tiên, Bờm thực hiện \(k\) lần bốc bi vào hộp (\(k \le 10^6\)), ở lần thứ \(i\), Bờm bốc \(a_i\) viên bi cho thêm vào ô \((x_i,y_i)\), tổng số bi Bờm bốc không vượt quá \(10^{12}\).

Bờm nhận thấy rằng nếu để các viên bi phân bố không đều trong các ô, sẽ có ô chứa quá nhiều viên bi gây khó khăn cho việc đóng hộp. Bờm bèn chế tạo một robot để di chuyển giữa các ô sao cho tất cả các ô trong hộp đều chứa số bi giống nhau. Robot của Bờm trong một giây có thể chuyển được đúng một viên bi từ một ô sang một ô khác chung đỉnh với ô đó (chú ý là không được chuyển bi ra khỏi hộp).

Yêu cầu: Tìm cách điều khiển robot để chia đều số bi trong hộp ra các ô trong thời gian ít nhất. Cho biết thời gian robot hoàn thành công việc theo phương án tìm được.

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\) cưhas ba số nguyên dương \(x_i,y_i,a_i\).

Output

• Một số nguyên duy nhất là thời gian robot hoàn thành công việc theo phương án tìm được. Trong trường hợp robot không thể chia đều số bi trong hộp ra các ô, in ra số \(-1\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(min(m,n) \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

4 3 6
2 1 1
2 2 4
2 2 4
2 3 2
3 2 9
3 3 4

17