Vận tải

Ruratania mới bước vào kinh tế thị trường và đang thiết lập những hoạt động kinh doanh mới trong nhiều lĩnh vực, trong đó có giao thông vận tải. Công ty giao thông vận tải TransRuratania đang bắt đầu thành lập một chuyến tàu tốc hành từ thành phố $A$ đến thành phố $B$ với một vài chỗ dừng tại các ga trên tuyến đường. Các ga được đánh số liên tiếp, ga của thành phố $A$ được đánh số $0$, ga của thành phố $B$ được đánh số $m$.

Công ty làm một thí nghiệm để nâng cao khả năng vận chuyển hành khách và từ đó nâng cao thu nhập. Chuyến tàu có thể chứa tối đa $n$ hành khách. Giá của một vé tàu bằng số các ga giữa ga xuất phát và ga đến, không tính ga xuất phát (bằng số hiệu ga đến trừ số hiệu ga xuất phát). Trước khi chuyến tàu bắt đầu hành trình từ thành phố $A$, các đơn đặt vé từ tất cả các ga trên đường đi được thu lại. Một đơn đặt vé từ ga $S$ bao gồm tất cả các vé đặt trước từ $S$ tới một ga đến xác định trước. Trong trường hợp công ty không thể tiếp nhận tất cả các đơn đặt vé vì khả năng chở khách có giới hạn, thì với mỗi đơn đặt vé công ty hoặc tiếp nhận hoàn toàn, hoặc từ chối hoàn toàn.

Tại mỗi ga, hành khách đến ga đó xuống tàu trước rồi hành khách xuất phát từ ga đó mới lên tàu, nên số hành khách trên tàu chỉ bị giới hạn trên từng đoạn đường giữa hai ga liên tiếp: trên mọi đoạn từ ga $j$ đến ga $j+1$, tổng số hành khách của các đơn được tiếp nhận có đi qua đoạn đó không được vượt quá $n$. Tàu chỉ chạy theo chiều từ $A$ đến $B$, nên đơn đặt vé có ga đến nhỏ hơn ga xuất phát không thể được tiếp nhận.

Yêu cầu: Cho trước danh sách các đơn đặt vé từ các ga trên tuyến đường từ $A$ đến $B$, hãy xác định thu nhập lớn nhất có thể của công ty TransRuratania. Thu nhập từ một đơn đặt vé được tiếp nhận là tích của số hành khách trong đơn với giá của vé tàu. Thu nhập của công ty là tổng thu nhập từ tất cả các đơn đặt vé được tiếp nhận.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n,m,d$ ($1\le n\le 5000$; $1\le m\le 10$; $1\le d\le 25$), lần lượt là sức chứa hành khách của tàu, số hiệu ga của thành phố $B$ và số đơn đặt vé từ tất cả các ga.
• Mỗi dòng trong $d$ dòng tiếp theo mô tả một đơn đặt vé gồm ba số nguyên: ga xuất phát, ga đến, số hành khách ($0\le$ ga xuất phát, ga đến $\le m$; ga xuất phát $\ne$ ga đến; $1\le$ số hành khách $\le n$).

Dữ liệu ra

In ra một số nguyên là thu nhập lớn nhất có thể.

Ràng buộc

• $1\le n\le 5000$, $1\le m\le 10$, $1\le d\le 25$.
• $0\le$ ga xuất phát, ga đến $\le m$; ga xuất phát $\ne$ ga đến.
• $1\le$ số hành khách của mỗi đơn $\le n$.

Ví dụ