선형 계획의 최댓값

크기가 $M\times N$인 정수 행렬 $A$, 길이가 $M$인 정수 벡터 $b=(b_1,b_2,\cdots,b_M)$, 길이가 $N$인 정수 벡터 $c=(c_1,c_2,\cdots,c_N)$이 주어진다. $A$의 행 번호는 $1$부터 $M$까지, 열 번호는 $1$부터 $N$까지이며, $i$행 $j$열의 원소를 $A_{i,j}$라고 한다.

길이가 $N$인 실수 벡터 $x=(x_1,x_2,\cdots,x_N)$가 $Ax\le b$와 $x\ge0$을 만족할 때, 목적함수 $c\cdot x$의 최댓값을 구해 보자. 벡터 사이의 부등식은 각 성분에 대해 성립해야 한다.

조건을 만족하는 $x$가 존재하지 않거나, 목적함수의 최댓값이 유한하지 않을 수도 있다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le1\,000)$

각 테스트 케이스의 첫 번째 줄에 정수 $M$, $N$이 공백으로 구분되어 주어진다. $(0\le M\le300; 0\le N\le100)$

두 번째 줄부터 $M$개의 줄에 걸쳐 행 번호 순서대로 정수 $A_{i,1}, A_{i,2}, \cdots, A_{i,N}$과 $b_i$가 공백으로 구분되어 주어진다. $(\lvert A_{i,j}\rvert\le1\,000; \lvert b_i\rvert\le1\,000)$

그다음 줄에 정수 $c_1, c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $(\lvert c_j\rvert\le1\,000)$ $N=0$이면 이 줄은 빈 줄이다. 입력 마지막에 연속한 빈 줄은 생략해도 된다.

모든 테스트 케이스에 대한 $MN$의 합은 $30\,000$ 이하이다. 채점 데이터는 정수로 주어진 계수의 수치 오차가 판정을 바꾸지 않도록 구성된다. 유한한 최댓값의 절댓값은 $10^{12}$ 이하이다.

각 테스트 케이스에 대해 조건을 만족하는 $x$가 없으면 INFEASIBLE을, 목적함수가 위로 유계가 아니면 UNBOUNDED를 한 줄에 출력한다. 그 외에는 OPTIMAL과 최댓값을 공백으로 구분하여 한 줄에 출력한다.

최댓값은 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.