1369: #2378. 「WC2001」高性能计算机

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

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

若节点 iii 连续处理 xxxAAA 类子任务,则对应的执行时间为:t=kiAx2t=k_i^Ax^2t=kiAx2
类似的,若节点i连续处理 xxxBBB 类子任务,对应的执行时间为:t=kiBx2t=k_i^Bx^2t=kiBx2

其中,kiAk_i^AkiA ​和 kiBk_i^BkiB ​是系数,单位是ns,i=1,2,⋯,pi=1,2,\cdots ,pi=1,2,,p

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

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

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

输入格式

第一行是对计算任务的描述,包括两个正整数 nAn_AnAnBn_BnB,分别是 AAA 类和 BBB 类子任务的数目,两个整数之间由一个空格隔开。

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

第二行是一个整数 ppp,即计算节点的数目。

随后连续的 ppp 行按顺序分别描述各个节点的信息,第 iii 个节点由第 i+2i+2i+2 行描述,该行包括下述四个正整数(相邻两个整数之间有一个空格):tiA,tiB,kiA,kiBt_i^A,t_i^B,k_i^A,k_i^BtiA,tiB,kiA,kiB

输出格式

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

样例

样例输入

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

样例输出

93

数据范围与提示

对于所有数据:
1nA60,1nB60
1p20
1tA1000,1tB1000,1kA50,1kB50