High Performance Parallel Task Scheduling

You are the chief engineer for a national high-performance parallel computer. A time‐critical engineering problem has been assigned to you. The large-scale computational task consists of two independent subtasks, denoted by \(A\) and \(B\). Each of these can be decomposed into many identical small subtasks. Note that all \(A\)–type subtasks have the same workload and all \(B\)–type subtasks have the same workload (the workload between \(A\) and \(B\) may differ). There is no precedence constraint either among the subtasks of the same type or between \(A\) and \(B\).

The supercomputer contains \(p\) computing nodes. Each node has a serial processor, local memory, and a high-speed cache. However, the computing nodes vary in performance. For this task, every node has three working states: standby, \(A\)–mode, and \(B\)–mode. In \(A\)–mode a node processes \(A\)–type subtasks; in \(B\)–mode, it processes \(B\)–type subtasks; in standby it does no computation. Initially, all nodes are on standby. Switching from standby to either \(A\) or \(B\) mode – or switching between \(A\) and \(B\) – incurs a startup time. For node \(i\) (\(1\le i\le p\)), the startup times are given by two positive integers \(t_i^A\) and \(t_i^B\) (measured in nanoseconds) for modes \(A\) and \(B\) respectively.

Once in a working mode, if node \(i\) processes \(x\) consecutive subtasks of type \(A\), the execution time (excluding state-switching overhead) is \(k_i^A x^2\) nanoseconds. Similarly, processing \(x\) consecutive \(B\)–type subtasks takes \(k_i^B x^2\) nanoseconds. Here \(k_i^A\) and \(k_i^B\) are positive integer coefficients. When a node’s task queue (which is decided before the computation starts) contains consecutive subtasks of the same type, they are executed together without interruption; however, if a node switches from one task type to the other within its queue, it must incur the appropriate startup time for the new type.

Your objective is to assign the subtasks among the \(p\) nodes – by determining an ordered task queue for each node (the queue being a string of \(A\) and \(B\) subtasks) – so that the overall completion time is minimized. The overall completion time is defined as the time when the last node finishes its assigned tasks. Note that the assignment must be completed before the computation begins and all nodes start simultaneously.

For convenience, the two large tasks have been decomposed into a total of \(m\) \(A\)–type subtasks and \(n\) \(B\)–type subtasks. In an individual node, if it processes only \(A\)–type tasks it does not incur the \(B\)–mode startup cost, and vice versa. However, if a node processes both types then both startup times are incurred. Formally, if node \(i\) is assigned \(a_i\) subtasks of type \(A\) and \(b_i\) subtasks of type \(B\), its finishing time is calculated as follows:

[ T_i = \begin{cases} ; t_i^A + k_i^A {a_i}^2, & \text{if } a_i > 0 \text{ and } b_i = 0, \ ; t_i^B + k_i^B {b_i}^2, & \text{if } b_i > 0 \text{ and } a_i = 0, \ ; t_i^A + k_i^A {a_i}^2 + t_i^B + k_i^B {b_i}^2, & \text{if } a_i > 0 \text{ and } b_i > 0, \ ; 0, & \text{if } a_i = 0 \text{ and } b_i = 0. \end{cases} ]

The goal is to determine a valid assignment of the \(m\) \(A\)–type subtasks and \(n\) \(B\)–type subtasks to the \(p\) nodes (where \(\sum_{i=1}^{p} a_i = m\) and \(\sum_{i=1}^{p} b_i = n\)) so that the maximum \(T_i\) across all nodes is minimized.

inputFormat

The first line contains three integers: \(p\) (the number of nodes), \(m\) (the number of \(A\)–type subtasks), and \(n\) (the number of \(B\)–type subtasks).

Then \(p\) lines follow. The \(i\)–th of these lines contains four positive integers: \(t_i^A\), \(t_i^B\), \(k_i^A\), and \(k_i^B\), representing the startup times and the quadratic cost coefficients for node \(i\) for tasks \(A\) and \(B\) respectively.

outputFormat

Output a single integer, the minimum possible overall completion time (in nanoseconds) after optimally assigning all subtasks.

sample

2 1 1
1 2 1 1
2 1 1 1

2