Task Assignment Optimization

In this problem, you are given ( n ) employees and ( m ) tasks. Each task ( i ) has an associated priority value ( p_i ). Additionally, you are given an ( n \times m ) capability matrix where the element at row ( i ) and column ( j ) is 1 if the ( i )-th employee can perform the ( j )-th task, and 0 otherwise. Your goal is to assign tasks to employees such that each employee is assigned at most one task and no task is assigned to more than one employee. You may also choose not to assign a task to some employees. The objective is to maximize the total priority of the assigned tasks. Formally, if you let ( task(j) ) denote the task assigned to the ( j )-th employee (if any), you need to maximize: [ \max \sum_{j=1}^{n} p_{task(j)} ] subject to each task being assigned at most once and employee ( j ) being assigned a task only if they are capable of performing it.

inputFormat

The input is given via stdin with the following format:

1. The first line contains two space-separated integers \( n \) and \( m \), representing the number of employees and tasks respectively.
2. The second line contains \( m \) space-separated integers representing the priority values \( p_0, p_1, \dots, p_{m-1} \) for each task.
3. The following \( n \) lines each contain \( m \) space-separated integers (either 0 or 1) representing the capability matrix. The \( j \)-th number in the \( i \)-th line is 1 if the \( i \)-th employee can perform the \( j \)-th task, and 0 otherwise.

outputFormat

The output, via stdout, should be a single integer – the maximum total priority achievable by an optimal assignment of tasks to employees.

4 5
10 5 6 10 8
1 0 1 0 1
0 1 0 1 1
1 0 0 0 1
0 1 1 1 0

34