MCM/ICM is just as interesting as ACM/ICPC.
……
Based on the previous question ( Escape LouvreⅠ) , we will optimize our previous model.
In the previous question, we assumed that everyone would only move and escape to the exit closest to him. This is a relatively good evacuation method, but it is obviously not the optimal evacuation method.
We consider this situation. If many people go to the same exit, the exit will become very crowded. A thin person may wait a lot of time near the exit. However, if he goes to a far exit, there may be no need to wait. So, the choice of export is also very important.
Qleonardo has solved this problem very well, but he wants to test you.
Now your task is to use your ingenuity to get as many people as possible to escape the Louvre and let the sum of time of people be the minimum.
The first line consists of three numbers m,
n(2<=n,m<=100) and p(1<=p<=500), representing the width and
length of the Louvre plane map and the number of initial people.
Next, a matrix of m*n, 0 means that a
certain position can go, 1 means an exit.
Next there are p lines, three numbers xi,
yi (1<=xi<=m,1<=yi<=n) and wi (0<=wi<=2^31-1) for each line,
indicating the initial position coordinates of the i-th person and his
strength.
The number of exports does not exceed 50.
The output includes one line and onenumber, indicating the minimum sum of time of each person.