| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 18 | 15 | 15 | 83.333% |
Albert는 최근 태양광으로 충전되는 배터리를 구입했는데, 이를 활용하여 전기를 아껴보려고 한다. 이 배터리는 충전하면서 동시에 사용할 수 없는 단점이 있다. 그래서 하루에 한 번 아침에 태양광 배터리를 충전 할지 혹은 사용할지 정하려고 한다 -- 이보다 더 자주 바꾸는 것은 너무 번거롭기 때문이다.
우선, 현재 배터리는 $B$만큼 충전된 상태이며 최대 충전량은 $C$이다. $i$번째 날에는 정확히 $D_i$ 만큼의 전기를 사용할 예정이다. 만약 $i$번째날 배터리의 충전량이 $D_i$ 이상이라면 배터리로 가전 제품을 사용할 수 있고, 배터리의 충전량은 $D_i$ 만큼 감소한다. 이 날은 일반 가정용 전기를 사용하지 않으므로 비용을 지불하지 않는다. 만약 $i$번째 날 배터리를 충전한다면 배터리의 충전량은 $P_i$ 만큼 증가하지만 최대 충전량인 $C$를 넘을 수 없다. 배터리를 충전하면서 동시에 사용할 수 없으므로, 이 날은 일반 가정용 전기를 사용하고 비용을 지불해야한다. Albert가 사는 곳의 전기 사용료는 매일 바뀌는데, $i$번째 날에는 단위 사용량 당 $F_i$만큼을 지불해야 하므로 총 $D_i \cdot F_i$ 를 지불해야한다.
위와 같은 조건 하에서 Albert는 앞으로 $N$일간 최소의 비용을 지불하고 동시에 $N$일째를 마쳤을 때 배터리 충전량이 처음 충전량보다 적지 않도록 하고 싶다 (즉 $N$일째를 마친 후 배터리는 $B$이상 충전 되어있어야 한다).
예를 들어 $N = 4,ドル $B = 0,ドル $C = 10,ドル $P = [10, 10, 10, 1],ドル $F = [100, 100, 100, 100],ドル $D = [4, 3, 2, 1]$이라 하자.
다른 예로 $N = 4,ドル $B = 10,ドル $C = 10,ドル $P = [10, 10, 10, 1],ドル $F = [100, 100, 100, 100],ドル $D = [4, 3, 2, 1]$이라 하자.
위와 같이 $N, B, C, P, F, D$ 정보가 주어졌을 때, Albert가 매일 필요한 만큼 전기를 사용하면서 $N$일째를 마쳤을 때 배터리 충전량이 처음 충전량보다 적지 않도록 할 때 최소로 지불해야하는 비용을 계산해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N,ドル $B,ドル $C$ 값이 순서대로 공백으로 구분되어 주어진다. 둘째 줄에는 매일 태양광을 통해 배터리를 얼마나 충전할 수 있는지 나타내는 배열 $P$가 공백으로 구분되어 주어진다. 셋째 줄에는 매일 변하는 전기 단위 사용료를 나타내는 배열 $F$가 공백으로 구분되어 주어진다. 넷째 줄에는 매일 사용할 전기량을 나타내는 배열 $D$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 최소 전기 사용료를 각 줄에 출력한다.
5 4 0 10 10 10 10 1 100 100 100 100 4 3 2 1 4 10 10 10 10 10 1 100 100 100 100 4 3 2 1 4 9 10 10 10 10 9 100 100 100 100 3 3 3 1 5 3 20 3 5 3 5 3 2 10 3 5 8 5 4 3 4 5 5 0 1 1 1 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000 1000 1000 1000 1000
400 300 100 39 5000000000000
예제 1-2: 본문에서 다루었다.
예제 3: 추가 설명 없음.
예제 4: 추가 설명 없음.
예제 5: 정답이 2,147,483,647를 넘길 수 있음에 주의하자.