Optimal Production Scheduling in a Dual-Stage Pipeline

A factory production line produces a product that requires two sequential operations: operation \(A\) and operation \(B\). The production line is organized as follows: a group of \(A\)-type machines takes workpieces from an input buffer, applies operation \(A\), and places the intermediate products into a buffer. Then, a group of \(B\)-type machines takes these intermediate products, applies operation \(B\), and finally places the finished products into an output buffer.

Each machine works independently and in parallel. However, different machines have different efficiencies; that is, each machine requires a fixed amount of time to process one workpiece for its corresponding operation. In one operation cycle, a machine processes exactly one workpiece. The total time for completing the operations is defined as the time when the last workpiece is finished.

Given the processing times of all machines for both operations and a target number \(N\) of workpieces to be processed, your task is to calculate:

1. The minimum time \(T_A\) needed for the \(A\)-type machines to finish processing \(N\) workpieces.
2. The minimum time \(T_B\) needed for the \(B\)-type machines to finish processing \(N\) workpieces.

For each group, a machine with processing time \(p\) can complete \(\lfloor T/p \rfloor\) operations within time \(T\). You need to determine the smallest \(T\) such that the sum of operations completed by all machines in that group is at least \(N\). Formally, for a group with machine times \(p_1, p_2, \ldots, p_k\), find the minimum \(T\) satisfying:

[ \sum_{i=1}^{k} \left\lfloor \frac{T}{p_i} \right\rfloor \ge N. ]

inputFormat

The input consists of the following lines:

1. The first line contains two integers \(N\) and \(M\), where \(N\) is the number of workpieces to process and \(M\) is the number of \(A\)-type machines.
2. The second line contains \(M\) integers representing the processing times of the \(A\)-type machines.
3. The third line contains one integer \(K\), the number of \(B\)-type machines.
4. The fourth line contains \(K\) integers representing the processing times of the \(B\)-type machines.

outputFormat

Output two integers separated by a space: the minimum finishing time for all \(A\) operations (\(T_A\)) and the minimum finishing time for all \(B\) operations (\(T_B\)).

sample

10 2
1 3
2
2 4

8 14