어느 공장에서 \(n\) 가지 제품을 생산한다. 제품 \(j\) 를 \(x_j\) 단위 생산하면 단위당 이익 \(c_j\) 가 발생하여 총 이익은 \(\sum_{j=1}^{n} c_j x_j\) 이다. 생산량 \(x_j\) 는 \(0\) 이상의 실수일 수 있다.

공장에는 \(m\) 가지 자원 제약이 있다. \(i\) 번째 자원은 총량이 \(b_i\) 로 한정되어 있으며, 제품 \(j\) 한 단위를 만들 때 자원 \(i\) 를 \(a_{ij}\) 만큼 소비한다. 따라서 각 자원 \(i\) 에 대해 $$ \sum_{j=1}^{n} a_{ij} x_j \le b_i $$ 를 만족해야 한다.

모든 제약을 지키면서 총 이익을 최대로 만들 때, 그 최댓값을 구하여라. 최적값은 항상 유리수이며, 기약분수 분자/분모 형태로 출력한다 (정수인 경우에도 분모를 \(1\) 로 하여 값/1 형태로 출력한다).

모든 \(c_j, a_{ij} \ge 0\) 이고 각 변수는 적어도 하나의 제약에서 양의 계수를 가지므로, 실현 가능 영역은 유계이며 최적값이 항상 존재한다.

\(1 \le n, m \le 40\)

\(0 \le c_j \le 1000\)

\(0 \le a_{ij} \le 1000\)

\(1 \le b_i \le 1000\)

각 변수 \(x_j\) 는 적어도 하나의 제약에서 양의 계수 \(a_{ij} > 0\) 을 가진다.

첫 줄에 두 정수 \(n\) 과 \(m\) 이 주어진다.

둘째 줄에 \(n\) 개의 정수 \(c_1, \dots, c_n\) 이 주어진다.

이어서 \(m\) 개의 줄에 각 제약이 주어진다. \(i\) 번째 줄에는 \(n+1\) 개의 정수 \(a_{i1}, a_{i2}, \dots, a_{in}, b_i\) 가 주어진다.

총 이익의 최댓값을 기약분수 분자/분모 형태로 한 줄에 출력한다.

riseoj 작성

출처 Original