Minimizing Total Employee Anger in Product Manufacturing

Your company has received a batch of orders requiring n types of products, numbered from 1 to n. For the i-th product, you must manufacture exactly C_i items. There are m employees available (numbered from 1 to m), but each employee can manufacture only certain types of products. Moreover, a product must be made entirely by one employee; it cannot be split among different employees.

The manufacturing capabilities are described by an m × n binary matrix \(A\), where \(A_{i,j}=1\) means that employee \(i\) can manufacture product \(j\) and \(A_{i,j}=0\) otherwise.

If an employee is given too many products, his anger increases. For employee \(i\), the anger cost is given by a piecewise linear function with \(S_i+1\) segments. In particular, if we denote \(T_{i,0}=0\) and \(T_{i,S_i+1}=+\infty\), then for the \(j\)-th segment \((1 \le j \le S_i+1)\), every product manufactured as the \(k\)-th unit with \(T_{i,j-1}+1 \le k \le T_{i,j}\) increases his anger by \(W_{i,j}\).

Your task is to assign the manufacturing orders to employees such that all product orders are fulfilled and the total anger of all employees is minimized. You only need to output the minimum possible total anger cost.

Note: If an employee can manufacture a product (i.e. \(A_{i,j}=1\)), any product of type \(j\) assigned to that employee will count toward his total production count, and the cost incurred will follow the segmented function described above.

Problem Summary

• There are n products with demands \(C_1, C_2, \dots, C_n\).
• There are m employees. Employee \(i\) can only produce product \(j\) if \(A_{i,j}=1\).
• Each employee \(i\) has a piecewise linear anger cost function defined by thresholds \(T_{i,1}, T_{i,2}, \dots, T_{i,S_i}\) (with \(T_{i,0}=0\) and \(T_{i,S_i+1}=+\infty\)) and costs \(W_{i,1}, W_{i,2}, \dots, W_{i,S_i+1}\).
• The goal is to minimize total anger cost over all employees while meeting product demands.

The problem can be modeled as a min-cost flow problem. For each product type and each employee, you can add edges if the employee is capable. The employee node will then have several edges to the sink representing each segment of the anger cost function, with capacities corresponding to \(T_{i,j} - T_{i,j-1}\) (and infinite capacity for the last segment) and cost \(W_{i,j}\) per unit flow.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ some reasonable limit), representing the number of product types and employees.

The second line contains n integers: C₁, C₂, ..., C_n, where C_i is the number of products of type i to be produced.

The following m lines each contain a binary string of length n. The \(j\)-th character of the \(i\)-th line is '1' if employee i can produce product j, and '0' otherwise.

Then, for each employee \(i\) from 1 to m, there are two parts:

• A line starting with an integer \(S_i\) (\(0 \le S_i \le\) a limit), followed by \(S_i\) integers: \(T_{i,1}, T_{i,2}, ..., T_{i,S_i}\). Here, \(T_{i,j}\) represents the upper bound of the \(j\)-th segment (with \(T_{i,0}=0\)).
• A line containing \(S_i+1\) integers: \(W_{i,1}, W_{i,2}, ..., W_{i,S_i+1}\), representing the anger cost per product in each segment.

It is guaranteed that a feasible assignment exists.

outputFormat

Output a single integer, which is the minimum possible total anger cost to fulfill all product orders.

sample

3 2
5 3 4
110
101
1 3
2 4
2 2
2 4
1 3 5

26