만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

태양광 충전

면접 대비

시간 제한0.5초메모리 제한512 MB

요약
매일 배터리를 충전하거나 사용하도록 정해 N일 뒤 잔량이 처음 값 이상이 되게 하는 최소 전기 요금을 구합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 구현
정답자
아직 제출이 없습니다

문제

Albert는 최근 태양광으로 충전되는 배터리를 구입했다. 이 배터리는 충전과 사용을 동시에 할 수 없다. 그래서 Albert는 하루에 한 번, 아침에 배터리를 충전할지 사용할지 정한다. 이보다 더 자주 바꾸면 번거롭기 때문이다.

현재 배터리 충전량은 BB이고 최대 충전량은 CC이다. ii번째 날에는 정확히 DiD_i만큼의 전기를 사용할 예정이다. ii번째 날 배터리 충전량이 DiD_i 이상이면 배터리로 가전제품을 사용할 수 있고, 충전량은 DiD_i만큼 줄어든다. 이 날은 일반 가정용 전기를 쓰지 않으므로 비용이 들지 않는다. ii번째 날에 배터리를 충전하면 충전량은 PiP_i만큼 늘어나지만 최대 충전량 CC를 넘을 수 없다. 충전과 사용을 동시에 할 수 없으므로, 충전하는 날에는 일반 가정용 전기를 쓰고 비용을 내야 한다. Albert가 사는 곳의 전기 사용료는 매일 바뀐다. ii번째 날의 단위 사용량당 요금은 FiF_i이므로, 그날 비용은 Di⋅FiD_i \cdot F_i이다.

위 조건에서 Albert는 앞으로 NN일 동안 매일 필요한 만큼 전기를 사용한다. NN일째를 마쳤을 때 배터리 충전량은 처음 충전량 BB보다 적지 않아야 한다. 이때 지불하는 전기 사용료의 합이 최소가 되는 값을 구하시오.

입력

입력 첫 줄에 테스트 케이스의 수 TT가 주어진다.

각 테스트 케이스의 첫 줄에 NN, BB, CC가 공백으로 구분되어 주어진다. 둘째 줄에는 매일 태양광으로 배터리를 얼마나 충전할 수 있는지 나타내는 배열 PP가 공백으로 구분되어 주어진다. 셋째 줄에는 매일 바뀌는 단위 전기 사용료를 나타내는 배열 FF가 공백으로 구분되어 주어진다. 넷째 줄에는 매일 사용할 전기량을 나타내는 배열 DD가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답, 즉 최소 전기 사용료를 한 줄에 하나씩 출력한다.

제한

  • 1≤T≤101 \le T \le 10
  • 1≤N,C≤10001 \le N, C \le 1000
  • 0≤B≤C0 \le B \le C
  • 1≤i≤N1 \le i \le N인 각 ii에 대하여:
    • 1≤Di,Pi≤10001 \le D_i, P_i \le 1000
    • 1≤Fi≤1091 \le F_i \le 10^9

예제1

  1. 예제 1

    입력
    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