에너지 × 시간 곱 최소화

Paulo는 Ábaco Computadores e Manutenções(ACM)라는 큰 회사에서 일한다. 전국 각지에 있는 ACM 고객사의 컴퓨터를 유지보수하는 일이라, 일주일에 꽤 많은 시간을 비행기 안에서 보낸다. 노트북은 늘 들고 다니고, 비행 중에도 업무를 처리한다.

노트북 배터리는 오래 가지 않는다. Paulo는 비행 중 배터리 사용 시간을 늘릴 방법을 찾다가, 최신 프로세서가 여러 단계의 주파수로 동작하며 성능과 소비 전력을 맞바꾼다는 사실을 알았다. 처음에는 주파수를 가장 낮은 단계로 고정해 보았다. 그러나 프로그램이 너무 느리게 돌아서 모든 작업을 끝낼 시간이 없었고, 남은 배터리는 쓸 곳이 없었다.

주파수 단계가 성능에 미치는 영향은 프로그램마다 다르다. 메모리, CPU, 입출력 중 무엇이 병목인지에 따라 달라진다. 최신 프로세서는 소프트웨어로 주파수 단계를 바꿀 수 있으므로, Paulo는 프로그램마다 주파수 단계를 따로 정해서 배터리 사용 시간을 늘리면서도 성능을 어느 정도 유지하려고 한다. 에너지와 성능을 함께 보는 지표로는 널리 쓰이는 에너지 × 시간 곱(EDP, Energy × Delay Product)을 쓴다.

Paulo에게는 순서대로 실행할 프로그램 목록과, 각 프로그램을 각 주파수 단계에서 실행할 때 드는 시간과 에너지, 주파수를 바꿀 때 드는 에너지가 모두 적혀 있다. 문제는 그가 다른 시스템 관리자와 마찬가지로 프로그래밍을 좋아하지 않는다는 점이다. 그래서 알고리즘과 프로그래밍에 능한 친구인 당신에게 도움을 청했다.

프로세서는 1번부터 F번까지 F개의 주파수 단계를 지원하고, 각 테스트 케이스가 시작될 때 1번 단계에 있다. 프로그램은 1번부터 P번까지 순서대로 실행한다. 프로그램 $p$를 $f$번 단계에서 실행하면 에너지 $E_{p,f}$ 줄과 시간 $A_{p,f}$ 밀리초가 들고, 이 실행의 EDP는 $E_{p,f} \times A_{p,f}$이다. 주파수 단계를 한 번 바꿀 때는 어느 단계에서 어느 단계로 바꾸든 에너지 $E$ 줄과 시간 $A$ 밀리초가 들고, 이 전환의 EDP는 $E \times A$이다. 전체 EDP는 실행 $P$번과 전환 전부의 EDP를 더한 값이다. 즉 프로그램 $p$를 $f_p$번 단계에서 실행하고 전환이 $C$번 일어났다면

$\text{EDP} = \sum_{p=1}^{P} E_{p,f_p} \times A_{p,f_p} + C \times E \times A$

이다. 전체 EDP를 최소로 만드는 실행 계획을 찾아 그 EDP를 구하는 프로그램을 작성하시오.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 네 개 $F$, $P$, $E$, $A$가 주어진다. $F$는 프로세서가 지원하는 주파수 단계의 수($1 \le F \le 20$), $P$는 순서대로 실행할 프로그램의 수($1 \le P \le 5000$), $E$는 주파수 단계를 한 번 바꾸는 데 드는 에너지(줄, $1 \le E \le 100$), $A$는 주파수 단계를 한 번 바꾸는 데 드는 시간(밀리초, $1 \le A \le 100$)이다. 주파수 단계는 1부터 $F$까지, 프로그램은 1부터 $P$까지의 정수로 구분한다.

다음 $P \times F$개의 줄에는 프로그램 정보가 프로그램마다 $F$줄씩 주어진다. 처음 $F$줄은 프로그램 1, 그다음 $F$줄은 프로그램 2에 해당하고, 나머지도 같은 순서다. 프로그램 $p$에 해당하는 $F$줄 중 $f$번째 줄에는 두 정수 $E_{p,f}$와 $A_{p,f}$가 주어진다. 각각 프로그램 $p$를 $f$번 주파수 단계에서 실행할 때 드는 에너지(줄)와 시간(밀리초)이며, $1 \le E_{p,f} \le 1000$, $1 \le A_{p,f} \le 1000$이다.

각 테스트 케이스가 시작될 때 프로세서는 1번 주파수 단계에 있다. 입력의 마지막에는 $F = P = E = A = 0$인 줄이 주어지고, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 프로그램 1번부터 $P$번까지 입력에 나온 순서대로 실행할 때의 최소 EDP를 출력한다.