30677번 - 반짝반짝 빛나는 별가루

문제

스타는 별가루를 만드는 마법 연습을 하는 중이다. 본인의 실력을 시험하기 위해 하루에 한 번씩, 총 $N$일 동안 마법을 사용하여 별가루를 얼마나 만들 수 있는지 확인하고자 했고 $N$일 동안의 계획을 세웠다.

스타는 별가루를 만들 수 있는 $K$가지의 마법을 사용할 수 있다. 각각의 마법을 1ドル$번 마법, 2ドル$번 마법, ... , $K$번 마법이라고 부르기로 하자.

$i$번 마법을 사용해서 만들 수 있는 별가루의 개수는 다음과 같다.

$\Delta Stardust = \lfloor base_i(1+\frac{combo \cdot C}{100})(1+\frac{skill_i \cdot s_i}{100}) \rfloor$

식에 대한 설명은 다음과 같다.

• $\Delta Stardust$: 만들어진 별가루의 개수이다.
• $base_i$: $i$번 마법을 사용해서 기본적으로 만들 수 있는 별가루의 개수이다.
• $combo$: 연속으로 마법을 사용한 횟수이다. 예를 들어, 오늘 마법을 사용하기 전에 마법을 5ドル$일 연속으로 사용했다면 $combo = 5$이다.
• $skill_i$: $i$번 마법의 숙련도이다. 예를 들어, 오늘 마법을 사용하기 전에 $i$번 마법을 사용한 경험이 3ドル$번 있으면 $skill_i = 3$이다.
• $C$와 $s_i$는 상수이다.

스타의 초기 피로도는 0ドル$이며, $i$번 마법을 사용할 때마다 스타의 피로도는 $p_i$만큼 상승한다. 피로도가 100ドル$을 초과하게 되면, 마법봉이 망가지고 이후에는 어떤 마법도 쓸 수 없게 된다. 동시에, 지금까지 만들었던 별가루도 못 쓰게 된다. 피로도는 휴식을 통해 줄일 수 있다. 휴식을 취하면 피로도가 $R$만큼 줄어들지만, 연속으로 마법을 사용한 횟수는 0ドル$이 된다. 피로도는 0ドル$ 미만으로 내려가지 않으며, 만약 휴식으로 감소하는 피로도가 현재 피로도보다 크다면 피로도는 0ドル$이 된다.

스타의 계획을 보고 $N$일 동안 만들 수 있는 별가루의 총 개수를 계산해 보자.

입력

첫째 줄에는 $N,K,C,R$ 이 공백을 사이에 두고 주어진다. $(1 \leq K \leq N \leq 100 ,円 000;$ 1ドル \leq C \leq 100;$ 1ドル \leq R \leq 100)$

둘째 줄에는 $base_1, \cdots , base_K$가 공백을 사이에 두고 주어진다. $(1 \leq base_i \leq 100 ,円 000)$

셋째 줄에는 $s_1, \cdots , s_K$가 공백을 사이에 두고 주어진다. $(1 \leq s_i \leq 100)$

넷째 줄에는 $p_1, \cdots ,p_K$가 공백을 사이에 두고 주어진다. $(1 \leq p_i \leq 100)$

다섯째 줄부터 $N$개의 줄에 걸쳐 스타가 $i$번째 날에 사용하려고 계획한 마법의 번호 $l_i \ (0 \leq l_i \leq K)$가 한 줄에 하나씩 주어진다. $l_i$가 0ドル$이면 그날 하루는 휴식을 취한다는 뜻이다.

입력으로 주어지는 모든 수는 정수이다.

출력

$N$일 동안 만들 수 있는 별가루의 총 개수를 출력한다. 계획 중간에 마법봉이 망가진다면 -1을 출력한다.

제한

힌트