题目描述

现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程师——来完成。为了尽可能充分发挥并行计算机的优势，我们的计算任务应当划分成若干个小的子任务。

这项大型计算任务包括 $A$ 和 $B$ 两个互不相关的较小的计算任务。为了充分发挥并行计算机的运算能力，这些任务需要进行分解。研究发现，$A$ 和 $B$ 都可以各自划分成很多较小的子任务，所有的 $A$ 类子任务的工作量都是一样的，所有的 $B$ 类子任务也是如此（$A$ 和 $B$ 类的子任务的工作量不一定相同）。$A$ 和 $B$ 两个计算任务之间，以及各子任务之间都没有执行顺序上的要求。

这台超级计算机拥有 $p$ 个计算节点，每个节点都包括一个串行处理器、本地主存和高速 cache。然而由于常年使用和不连贯的升级，各个计算节点的计算能力并不对称。一个节点的计算能力包括如下几个方面：

1. 就本任务来说，每个节点都有三种工作状态：待机、$A$ 类和 $B$ 类。其中，$A$ 类状态下执行 $A$ 类任务；$B$ 类状态下执行 $B$ 类任务；待机状态下不执行计算。所有的处理器在开始工作之前都处于待机状态，而从其它的状态转入 $A$ 或 $B$ 的工作状态（包括 $A$ 和 $B$ 之间相互转换），都要花费一定的启动时间。对于不同的处理节点，这个时间不一定相同。用两个正整数 $t_{i}^{A}$ ​和 $t_{i}^{B}$ ($i = 1,2,\cdots,p$)分别表示节点 $i$ 转入工作状态 $A$ 和工作状态 $B$ 的启动时间（单位：ns）。

2. 一个节点在连续处理同一类任务的时候，执行时间——不含状态转换的时间——随任务量（这一类子任务的数目）的平方增长，即：

若节点 $i$ 连续处理 $x$ 个 $A$ 类子任务，则对应的执行时间为：$t = k_{i}^{A} x^2$；

类似的，若节点 $i$ 连续处理 $x$ 个 $B$ 类子任务，对应的执行时间为：$t = k_{i}^{B} x^2$。

其中，$k_{i}^{A}$ ​和 $k_{i}^{B}$ ​是系数，单位是 ns，$i=1,2,\cdots,p$。

任务分配必须在所有计算开始之前完成，所谓任务分配，即给每个计算节点设置一个任务队列，队列由一串 $A$ 类和 $B$ 类子任务组成。两类子任务可以交错排列。

计算开始后，各计算节点分别从各自的子任务队列中顺序读取计算任务并执行，队列中连续的同类子任务将由该计算节点一次性读出，队列中一串连续的同类子任务不能被分成两部分执行。

现在需要你编写程序，给这 $p$ 个节点安排计算任务，使得这个工程计算任务能够尽早完成。假定任务安排好后不再变动，而且所有的节点都同时开始运行，任务安排的目标是使最后结束计算的节点的完成时间尽可能早。

输入格式

第一行是对计算任务的描述，包括两个正整数 $n_A$ 和 $n_B$，分别是 $A$ 类和 $B$ 类子任务的数目，两个整数之间由一个空格隔开。

后面部分是对此计算机的描述：

第二行是一个整数 $p$，即计算节点的数目。

随后连续的 $p$ 行按顺序分别描述各个节点的信息，第 $i$ 个节点由第 $i+2$ 行描述，该行包括下述四个正整数（相邻两个整数之间有一个空格）：$t_{i}^{A},t_{i}^{B},k_{i}^{A},k_{i}^{B}$。

输出格式

只有一行，包含有一个正整数，即从各节点开始计算到任务完成所用的时间。

5 5
3
15 10 6 4
70 100 7 2
30 70 1 6

93

提示

对于所有数据： $1 \le n_A \le 60$，$1 \le n_B \le 60$，$1 \le p \le 20$，$1 \le t_{i}^{A} \le 1000$，$1 \le t_{i}^{B} \le 1000$，$1 \le k_{i}^{A} \le 50$，$1 \le k_{i}^{B} \le 50$。