Job Shop Scheduling with Precedence and Machine Constraints

You are given n jobs and m machines. Each job consists of m operations. The k-th operation of a job must be processed on a specified machine for a given processing time. We denote an operation as j-k where j (1 ≤ j ≤ n) is the job number and k (1 ≤ k ≤ m) is the operation number.

A scheduling order is provided as a sequence of n*m job numbers. Since each job’s operations must be processed in order, the i-th occurrence of a job number in the sequence corresponds to its i-th operation. However, the scheduling order only dictates the order in which operations are to be inserted into the machine schedules – it does not necessarily correspond to the actual execution order.

The insertion of an operation must obey the following constraints:

1. For the same job, an operation cannot start until its preceding operation is completed. Mathematically, for job j, the k-th operation can start no earlier than the finish time of the (k-1)-th operation.
2. At any given time, each machine can process at most one operation.

When inserting an operation into its designated machine timeline, you must schedule it as early as possible while satisfying the above constraints. Furthermore, if multiple gaps are available for insertion, the operation should be inserted into the earliest gap.

Your task is to simulate the scheduling process according to the given ordering and these rules, and determine the total time required to complete all operations. All formulas in this problem are given in LaTeX format. For example, the constraints above can be written as:

1. For the same job, operation \(k\) cannot start before operation \(k-1\) finishes.
2. At any time, each machine can process at most one operation.

Example:

For \(n=3\) and \(m=2\), suppose the processing information is provided in the table below:

The scheduling order provided is: 1 1 2 3 3 2 (i.e. first schedule job 1's operation 1, then job 1's operation 2, then job 2's operation 1, etc.). Under the above "earliest insertion" rules, the unique valid schedule completes all operations in a total time of 10.

Your program should output the total processing time required for the given scheduling order.

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(m\) (the number of jobs and machines).
2. The next \(n\) lines each contain \(2m\) integers. For the i-th job, the line contains \(m\) pairs. Each pair consists of two integers: the machine number on which the corresponding operation is processed and the processing time required for that operation.
3. The last line contains \(n*m\) integers which represent the scheduling order. The \(i\)-th occurrence of a job number in this sequence corresponds to the operation index (from \(1\) to \(m\)) of that job.

Note: Job and machine numbers are 1-indexed.

outputFormat

Output a single integer: the total time required to finish all operations under the given scheduling constraints and the earliest possible insertion rule.

sample

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

10