에너지 사용량

전기 에너지의 가격은 공급과 수요에 따라 변동한다. 위젯을 생산하는 24시간 공장의 관리자인 Homer는 공장 운영에 드는 에너지 비용을 최소화하려 한다. Homer는 가격을 통제할 수도, 위젯 생산에 필요한 에너지의 양을 바꿀 수도 없다. 하지만 공장에는 햇빛을 에너지로 변환하는 태양광 패널이 설치되어 있다. Homer는 에너지를 저장했다가 나중에 사용할 수 있도록 용량이 $B$메가와트시(MWh)인 배터리를 구매하는 것을 고려하고 있다. 그는 이러한 구매가 재정적으로 타당한지 알고 싶어 한다.

Homer는 과거 데이터를 사용하여 앞으로 $N$시간에 대한 다음 정보를 예측한다(아래의 $1 \leq i \leq N$):

• $p_i$: $i$번째 시간의 에너지 가격(달러/MWh)

• $r_i$: $i$번째 시간에 공장을 운영하는 데 필요한 에너지의 양(MWh)

• $s_i$: $i$번째 시간에 태양광 패널이 생성하는 에너지의 양(MWh)

또한 Homer는 배터리가 처음에는 비어 있다고 가정한다.

각 시간마다 Homer는 그 시간의 에너지 요구량을 충족하기 위해 다음 행동 중 하나 이상을 수행할 수 있다.

• 생성된 태양 에너지의 일부를 사용한다.

• 배터리에 저장된 에너지의 일부를 사용한다.

• 전력 회사에서 에너지를 구매하고, 구매한 MWh당 $p_i$을 지불한다.

그 시간의 에너지 요구량을 충족한 후, Homer는 다음 행동 중 하나 이상을 수행할 수도 있다.

• 잉여 에너지(잉여 태양 에너지, 잉여 구매 에너지, 배터리에 저장된 에너지를 합친 것)의 일부를 배터리 용량 이하로 배터리에 저장한다.

• 잉여 에너지의 일부를 판매한다. 매시간 전력 회사에는 $M$개의 에너지 환매 요금제가 있다. $j$번째 환매 요금제에서는 Homer가 정확히 정확히 $d_{i,j}$MWh를 $c_{i,j}$에 판매할 수 있다. 시간마다 최대 하나의 요금제를 선택할 수 있다.

• 잉여 에너지의 일부를 낭비한다.

Homer가 앞으로 $N$시간 동안 공장을 운영하는 데 필요한 최소 비용을 구하라. $N$번째 시간이 끝났을 때 배터리에 남아 있는 에너지는 모두 낭비된 것으로 간주한다. 비용이 음수라면 Homer가 이익을 낼 수 있다는 뜻이다.

첫 줄에는 세 정수 $N$ $(1 \leq N \leq 1\,000)$, $M$ $(1 \leq M \leq 10)$, $B$ $(1 \leq B \leq 20)$가 주어진다. 여기서 $N$는 시간의 수, $M$는 각 시간에 이용할 수 있는 환매 요금제의 수, $B$는 배터리의 용량이다.

다음 $N$개의 줄에는 각각 세 정수 $p_i$, $r_i$, $s_i$ $(1 \leq p_i, r_i, s_i \leq 100)$가 주어진다. 여기서 $p_i$는 $i$번째 시간의 에너지 가격, $r_i$는 $i$번째 시간에 공장을 운영하는 데 필요한 에너지, $s_i$는 $i$번째 시간에 생성되는 태양 에너지의 양이다.

다음 $N$개의 줄에는 각각 $M$개의 정수 $1 \leq c_{i,j} \leq 10\,000$가 주어진다. 여기서 $c_{i,j}$는 $i$번째 시간의 $j$번째 환매 요금제의 가격이다.

다음 $N$개의 줄에는 각각 $M$개의 정수 $1 \leq d_{i,j} \leq 100$가 주어진다. 여기서 $d_{i,j}$는 $i$번째 시간의 $j$번째 환매 요금제로 판매할 수 있는 에너지의 양(MWh)이다.

앞으로 $N$시간 동안 공장을 운영하는 데 필요한 최소 비용을 출력한다.