Farmer pittoresque 的农场里种了两种水果：苹果和香蕉。每年秋天，pittoresque 都需要走进农场采摘这些美味的水果。然而，作为一个香蕉爱好者，pittoresque 只关心收集香蕉，并不在乎他采摘了多少苹果。

农场可以建模为一个图，其中顶点是苹果树或香蕉树，此外还有一个表示农场入口的顶点。为了准备采摘，pittoresque 需要在顶点之间修建（双向）道路。道路的修建必须满足从入口出发可以到达每一棵香蕉树。作为一个敬业的人，pittoresque 在修建道路时会获得一些幸福感，尽管这会消耗一些能量。不同的道路所消耗的能量和获得的幸福感可能不同。尽管如此，pittoresque 不想修建形成环的道路，也不想修建他无法到达的道路。最后，pittoresque 希望在修建道路后，最大化所获得的幸福感总和与所消耗的能量总和之比。

输入格式

第一行包含两个整数 $a$ 和 $b$ ($0 \le a \le 10, 1 \le b \le 100$)，分别表示苹果树的数量和香蕉树的数量。你可以假设苹果树的编号为 $1, \dots, a$，香蕉树的编号为 $a + 1, \dots, a + b$，入口的编号为 $a + b + 1$。

下一行包含一个整数 $m$ ($b \le m \le 1000$)，表示可以修建的道路数量。

接下来的 $m$ 行包含有关可以修建的道路的信息。每行包含四个整数 $u, v, h, e$ ($1 \le u, v \le a + b + 1, u \neq v, 0 \le h \le 10^6, 1 \le e \le 10^6$)。这意味着如果修建一条连接 $u$ 和 $v$ 的道路，将消耗 $e$ 的能量并获得 $h$ 的幸福感。

保证从入口出发可以到达每一棵香蕉树。两个顶点之间可能存在多条道路。

输出格式

在满足上述所有约束条件的道路修建方案中，所获得的幸福感总和与所消耗的能量总和之比的最大值可以表示为 $P/Q$，其中 $P$ 和 $Q$ 是互质的整数。为了方便起见，你只需要输出 $P \times Q$。

样例

样例输入 1

1 3
4
1 2 10 1
2 3 10 1
3 4 10 1
1 5 10 1

样例输出 1

10

样例输入 2

1 3
5
1 2 100000 1
2 3 0 20
3 4 1 1
4 5 1 1
2 5 1 400

样例输出 2

2300046