**Problem**

You are given two integers N and M, representing the dimensions of a grid. There are K special cells in the grid. Each special cell has some value associated with it. A special cell is represented by Xi, Yi, Vi, describing the (x,y) coordinates of the cell and the value V. Your task is to find the sum of the values of all paths starting from (1, 1) to (N, M) and travelling only right or down to a neighbouring cell.

**Example 1**

**Input:**

N = 2, M = 3, K = 2

X1 = 1, Y1 = 2, V1 = 1

X1 = 2, Y1 = 3, V1 = 1

**Output: **5

**Explanation:**

The above image represents the grid. There are total 3 paths from (1, 1) to (2, 3):

- (1, 1) -> (1, 2) -> (1, 3) -> (2, 3). The sum of the values of all the cells in this path is 1 + 1 = 2.
- (1, 1) -> (1, 2) -> (2, 2) -> (2, 3). The sum of the values of all the cells in this path is 1 + 1 = 2.
- (1, 1) -> (2, 1) -> (2, 2) -> (2, 3). The sum of the values of all the cells in this path is 1.

Therefore, the sum of the values of all paths is 2 + 2 + 1 = 5.

**Example 2**

**Input:**

N = 3, M = 3, K = 2

X1 = 1, Y1 = 2, V1 = 2

X1 = 2, Y1 = 2, V1 = 1

**Output: **10

**Explanation:** The sum of the values of all paths in the above grid is 9.

**Naive Approach**

We will try to find the contribution of every cell to the sum of the values of all paths in the grid. For example, for a cell with coordinates (i, j), we need to calculate the number of paths from (1, 1) to (N, M) in which this cell appears. Then, its contribution to the answer will be the number of paths * value of (i, j). We can do this for every (i, j) to get the sum of the values of all paths in the grid.

Any path that passes through (i, j) can be broken down into two paths:

(1, 1) -> (i, j) and (i, j) -> (N, M).

Let K1 be the number of ways to reach (i, j) from (1, 1) and K2 be the number of ways to reach (N, M) from (i, j). The total number of paths from (1, 1) to (N, M) that pass through (i, j) will be K1 * K2.

We can calculate the values of K1 and K2 using dynamic programming. Let DP[i][j] be the number of paths from (1, 1) to (i, j). For any cell (i, j), we can reach it either from (i-1, j) or from (i, j-1). So, DP[i][j] = DP[i-1][j] + DP[i][j-1].

**Implementation**

```
#include "bits/stdc++.h"
using namespace std;
// Function to find the sum of the values of all paths
void solve(int n, int m, int k, vector<vector<int>> pts){
// Dp[i][j] = number of ways to reach i,j
int dp[n][m];
memset(dp, 0, sizeof(dp));
dp[0][0]=1;
for(int i=0; i<n; i++){
for (int j=0; j<m; j++){
// Calculating dp[i][j] = dp[i-1][j] + dp[i][j-1]
if (i!=0) dp[i][j] += dp[i-1][j];
if (j!=0) dp[i][j] += dp[i][j-1];
}
}
// Initialising answer
int ans = 0;
for (int i=0; i<k; i++){
int x = pts[i][0]-1, y = pts[i][1]-1, v = pts[i][2];
// K1 = no. of paths from (1, 1) to (i, j)
int k1 = dp[x][y];
// K2 = no. of paths from (i, j) to (1, 1)
int k2 = dp[n-x-1][m-y-1];
// ans = value * k1 * k2
ans += k1 * k2 * v;
}
// Printing the sum of the values of all paths.
cout<<ans<<endl;
}
// Driver Code
int main(){
int n = 3, m = 3, k = 2;
vector<vector<int>> pts = {{1, 2, 2}, {2, 2, 1}};
solve(n, m, k, pts);
return 0;
}
```

**Output**

`10`

**Time Complexity**

We have iterated over N and M to calculate the DP matrix, so its time complexity will be O(N * M). Then, we iterated over K and calculated the contribution of each point to the final sum of the values of all paths in O(1). So the total time taken will be O(N * M + K). Since K will always be less than N * M, we can write the time complexity as O(N * M).

**Space Complexity**

We have used a DP matrix to calculate the number of paths from (1, 1) to (i, j), so the space complexity is O(N * M).