\(N\)명의 작업자와 \(M\)개의 작업이 있다. 작업자 \(i\)는 최대 \(\text{cap}_i\) 단위의 일을 처리할 수 있고, 작업 \(j\)는 정확히 \(d_j\) 단위가 처리되어야 한다. 작업자 \(i\)가 작업 \(j\)를 한 단위 처리할 때마다 \(c_{i,j}\)의 비용이 든다(한 작업자가 여러 작업을, 한 작업이 여러 작업자에 의해 분담될 수 있다).

모든 작업의 요구량을 정확히 채우는 것이 가능하면 최소 총비용을, 불가능하면 -1을 출력하라.

\(1 \le N,M \le 100\), \(0 \le \text{cap}_i \le 1000\), \(1 \le d_j \le 1000\), \(0 \le c_{i,j} \le 10^4\)

첫 줄에 \(N\), \(M\). 둘째 줄에 \(\text{cap}_1 \dots \text{cap}_N\). 셋째 줄에 \(d_1 \dots d_M\). 다음 \(N\)개의 줄에 각 줄 \(M\)개의 정수 \(c_{i,j}\).

최소 총비용 또는 불가능하면 -1을 한 줄에 출력한다.

riseoj 작성

출처 Original