몇몇 소녀들은 큐베와 계약해서 소원을 이루게 되고, 그 대신에 마법소녀가 된다. 사용하는 마법의 형태 및 효과는 소원에 강하게 영향을 받는다. 마법소녀 사야카 쨩은 최근 큐베와 계약한 신참 마법소녀다. 사야카의 소원은 “사고로 인해 손가락을 움직일 수 없게 되어버려서 음악 연주를 포기한 남자아이를 도와주는 것”이었기 때문에, 사용하는 마법진이 원 모양으로 음표가 배열되어 있는 모양이다.
사야카는 $N$ 개의 음표를 가지고 있어서, 이 음표들을 원 모양으로 배열해서 마법진을 만든다. 음표를 어떤 순서로 배열할지는 사야카가 자유롭게 정할 수 있다. 마법진을 만들기 위해서는 정신력을 소모해야 하며, 소모되는 정신력의 양은 음표의 배치에 따라 아래와 같이 결정된다.
음악적 아름다움의 값이 $M$ 개의 양의 정수 $S_1, \cdots, S_M$으로 정해져 있다.
각 음표는 음정을 가지고 있으며, 음정은 $1$ 이상 $M$ 이하의 정수 $K_1, \cdots, K_N$으로 나타낸다.
음정이 $a$, $b$ ($a \leq b$)인 두 음표 사이의 반발력은 $\left\lfloor(S_a + \cdots + S_b)/L\right\rfloor$로 정의된다. 이때, $L$은 입력에서 주어지는 정수이며, 실수 $x$에 대해 $\left\lfloor x\right\rfloor$는 $x$를 넘지 않는 최대의 정수를 나타낸다.
사야카가 소모하는 정신력은 $N$ 개의 인접한 두 음표쌍들에 대해 반발력의 합이 된다.
예를 들어, 음악적 아름다움이 각각 $\{100, 200, 300, 400, 500\}$이고, $L = 99$일 때, 음정이 $\{1, 3, 5, 4\}$인 음표들을 이 순서대로 배열해 마법진을 만드는 경우 소모되는 정신력은 $37$ ($=\left\lfloor(100+200+300)/99\right\rfloor+\left\lfloor(300+400+500)/99\right\rfloor+\left\lfloor(500+400)/99\right\rfloor+\left\lfloor(400+300+200+100)/99\right\rfloor$) 이다.
사용할 음표들의 음정과, 각 음정의 음악적 아름다움이 주어질 때, 소모되는 정신력의 최솟값을 구하자.
입력
첫 번째 줄에 $3$개의 정수 $N$, $M$, $L$이 주어진다. $N$은 사야카가 가지고 있는 음표의 수, $M$은 음악적 아름다움의 값의 개수, $L$은 반발력을 계산하는 데 사용하는 정수이다. ($3 \leq N \leq 2\,000$, $1 \leq M \leq 100\,000$, $1 \leq L \leq 100\,000$)
두 번째 줄에는 음표의 음정을 나타내는 $N$개의 정수 $K_1, K_2, \cdots, K_N$이 주어진다. ($1 \leq K_i \leq M$)
세 번째 줄에는 음악적 아름다움을 나타내는 $M$개의 정수 $S_1, S_2, \cdots, S_M$이 주어진다. ($1 \leq S_i \leq 100\,000$)
sait2000 3년 전 8
몇몇 소녀들은 큐베와 계약해서 소원을 이루게 되고, 그 대신에 마법소녀가 된다. 사용하는 마법의 형태 및 효과는 소원에 강하게 영향을 받는다. 마법소녀 사야카 쨩은 최근 큐베와 계약한 신참 마법소녀다. 사야카의 소원은 “사고로 인해 손가락을 움직일 수 없게 되어버려서 음악 연주를 포기한 남자아이를 도와주는 것”이었기 때문에, 사용하는 마법진이 원 모양으로 음표가 배열되어 있는 모양이다.
사야카는 $N$ 개의 음표를 가지고 있어서, 이 음표들을 원 모양으로 배열해서 마법진을 만든다. 음표를 어떤 순서로 배열할지는 사야카가 자유롭게 정할 수 있다. 마법진을 만들기 위해서는 정신력을 소모해야 하며, 소모되는 정신력의 양은 음표의 배치에 따라 아래와 같이 결정된다.
예를 들어, 음악적 아름다움이 각각 $\{100, 200, 300, 400, 500\}$이고, $L = 99$일 때, 음정이 $\{1, 3, 5, 4\}$인 음표들을 이 순서대로 배열해 마법진을 만드는 경우 소모되는 정신력은 $37$ ($=\left\lfloor(100+200+300)/99\right\rfloor+\left\lfloor(300+400+500)/99\right\rfloor+\left\lfloor(500+400)/99\right\rfloor+\left\lfloor(400+300+200+100)/99\right\rfloor$) 이다.
사용할 음표들의 음정과, 각 음정의 음악적 아름다움이 주어질 때, 소모되는 정신력의 최솟값을 구하자.
입력
첫 번째 줄에 $3$개의 정수 $N$, $M$, $L$이 주어진다. $N$은 사야카가 가지고 있는 음표의 수, $M$은 음악적 아름다움의 값의 개수, $L$은 반발력을 계산하는 데 사용하는 정수이다. ($3 \leq N \leq 2\,000$, $1 \leq M \leq 100\,000$, $1 \leq L \leq 100\,000$)
두 번째 줄에는 음표의 음정을 나타내는 $N$개의 정수 $K_1, K_2, \cdots, K_N$이 주어진다. ($1 \leq K_i \leq M$)
세 번째 줄에는 음악적 아름다움을 나타내는 $M$개의 정수 $S_1, S_2, \cdots, S_M$이 주어진다. ($1 \leq S_i \leq 100\,000$)
출력
소모되는 정신력의 최솟값을 출력한다.