30971번 - 육회비빔밥

문제

진주 나들이를 온 보선이는 배가 너무 고파 육회비빔밥을 먹기 위해 진주 대안동에 갔다. 그런데 이게 웬 떡? 육회비빔밥 시식 행사가 진행 중이었다. 대식가이자 미식가인 보선이는 육회비빔밥을 감칠맛이 최대한 나게끔 전부 먹으려고 한다. 하지만 전부 먹으려고 하니 아무리 뻔뻔한 보선이라도 시식대 직원의 눈치가 조금 보이기 시작했다. 그래서 각 시식대의 정보를 파악해서 전략적으로 먹기로 했다.

육회비빔밥 시식대는 총 $N$개가 있다. 각 시식대에는 육회비빔밥 한 그릇과 직원 1명이 있으며, 육회비빔밥의 단맛과 짠맛 그리고 그곳에 있는 직원이 눈치 주는 정도는 수치로 나타낼 수 있다. 보선이는 육회비빔밥이 남아 있는 시식대 중 하나를 골라서 갈 수 있으며, 한 시식대에 갈 때마다 그곳에 있는 육회비빔밥은 무조건 다 먹어야 한다.

보선이가 $i$번째로 간 시식대에 있는 육회비빔밥의 단맛과 짠맛을 각각 $A_i,ドル $B_i$라고 하였을 때, 보선이가 느낄 수 있는 총 감칠맛은 다음과 같이 정해진다.$$\sum_{i=2}^{N} \pmatrix{A_{i-1} \times B_i}$$

또한, 보선이는 첫 번째로 간 시식대에서는 눈치를 받지 않으나 두 번째로 간 시식대부터는 눈치를 받게 된다. 구체적으로, $i$번째로 간 시식대에 있는 직원이 눈치 주는 정도를 $C_i$라고 하였을 때, $i(i≥2)$번째로 간 시식대에서 보선이가 눈치 받는 정도는 \(C_{i-1} \times C_i\)가 된다. 하지만 보선이는 $K$만큼의 뻔뻔함의 정도를 지니고 있어서, 눈치 받는 정도가 $K$ 이하라면 아랑곳하지 않고 그곳에 있는 육회비빔밥을 먹는다. 그렇지만 눈치 받는 정도가 K를 넘게 되면 그곳에 있는 육회비빔밥을 먹지 못하고 시식을 중단하게 된다.

위와 같은 조건들을 고려해서 보선이가 육회비빔밥 $N$그릇을 다 먹었을 때 느낄 수 있는 총 감칠맛의 최댓값을 구해보자.

입력

첫 번째 줄에는 시식대의 개수 $N,ドル 보선이의 뻔뻔함의 정도 $K$가 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 10; 1 ≤ K ≤ 100)$

두 번째 줄에는 각 시식대에 있는 육회비빔밥의 단맛 $A_1,ドル $\dots,ドル $A_N$이 공백으로 구분되어 주어진다. $(1 ≤ A_i ≤ 10)$

세 번째 줄에는 각 시식대에 있는 육회비빔밥의 짠맛 $B_1,ドル $\dots,ドル $B_N$이 공백으로 구분되어 주어진다. $(1 ≤ B_i ≤ 10)$

네 번째 줄에는 각 시식대에 있는 직원의 눈치 주는 정도 $C_1,ドル $\dots,ドル $C_N$이 공백으로 구분되어 주어진다. $(1 ≤ C_i ≤ 10)$

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

출력

첫 번째 줄에 보선이가 육회비빔밥 $N$그릇을 다 먹었을 때 느낄 수 있는 총 감칠맛의 최댓값을 출력한다. 만약 육회비빔밥 $N$그릇을 다 먹을 수 없다면 –1을 출력한다.

제한

노트

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.