在二维平面上，你最初位于 $(0, 0)$，并且想要前往 $(N, M)$。如果你当前的位置是 $(x, y)$，你可以在下一步走向 $(x + 1, y)$ 或 $(x, y + 1)$。你行走的路径定义为依次连接每一步的位置所形成的从 $(0, 0)$ 到 $(N, M)$ 的折线。

有 $K$ 个矩形。第 $i$ 个矩形的左下角和右上角坐标分别为 $(x_{i,1} - 0.5, y_{i,1} - 0.5)$ 和 $(x_{i,2} + 0.5, y_{i,2} + 0.5)$。如果你的行走路径与该矩形的左边界和右边界都相交，你必须承担 $a_i$ 的代价；如果路径与该矩形的上边界和下边界都相交，你必须承担 $b_i$ 的代价。总代价定义为每个矩形产生的代价之和。

你需要求出从 $(0, 0)$ 前往 $(N, M)$ 所需的最小总代价。

输入格式

第一行包含三个整数 $N$，$M$ 和 $K$（$1 \le N, M \le 50$，$1 \le K \le 2000$）。

接下来的 $K$ 行，每行包含六个整数。第 $i$ 行包含六个整数 $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}, a_i, b_i$，描述第 $i$ 个矩形的位置和代价。保证 $0 \le x_{i,1} \le x_{i,2} \le N$，$0 \le y_{i,1} \le y_{i,2} \le M$，且 $0 \le a_i, b_i \le 10^4$。

输出格式

输出一个整数，表示从 $(0, 0)$ 前往 $(N, M)$ 所需的最小总代价。

样例

输入样例 1

1 2 1
0 1 1 1 1 2

输出样例 1

2

输入样例 2

4 2 6
0 1 2 1 3 3
0 1 4 1 2 9
1 0 1 2 4 6
3 0 3 2 6 2
2 0 3 2 5 1
1 0 2 1 6 0

输出样例 2

27