34008번 - 아즈모스 협곡 탐험

문제

...하지만, 이내 깨달았지. 그날 우리가 마주한 건 강력한 힘이 아닌, 거대한 절망이었음을.

아즈모스, 이제 이 땅에 메아리치는 건, 저주로 물든...절규뿐이야.

아즈모스 협곡은 모험과 위험이 가득한 신비로운 지역이다. 메린이 멘보롱은 귀중한 보상을 얻기 위해 이 험난한 협곡에 도전하기로 결심했다. 하지만 협곡은 함정과 몬스터로 가득 차 있기 때문에, 철저한 계획 없이는 끝까지 탐험할 수 없다.

아즈모스 협곡은 세 줄로 구성된 벌집 형태의 맵이다. 각 줄의 구조는 다음과 같다.

• 윗줄은 총 $N$개의 칸으로 구성되며, $(1, i)$ 위치에 존재한다. $(1 \le i \le N)$
• 중앙줄은 $(2, 0)$이 [START], $(2, N+2)$가 [GOAL]이며, 그 사이에는 $(2, i)$ 위치의 칸들이 존재한다. $(1 \le i \le N+1)$
• 아랫줄은 총 $N$개의 칸으로 구성되며, $(3, i)$ 위치에 존재한다. $(1 \le i \le N)$

각 칸에서는 인접한 오른쪽 위, 오른쪽, 오른쪽 아래 셋 중 하나로 이동할 수 있다. 보다 엄밀한 표현으로는 다음과 같다:

• [START]에서는 $(2, 1)$로만 이동 가능하다.
• $(2, N+1)$에서는 [GOAL]으로만 이동 가능하다.
• $(1, i)$에서는 $(1, i+1)$ 또는 $(2, i+1)$로 이동 가능하다. $(1 \leq i \leq N-1)$
• $(2, i)$에서는 $(1, i),ドル $(2, i+1),ドル 또는 $(3, i)$로 이동 가능하다. $(1 \leq i \leq N)$
• $(3, i)$에서는 $(2, i+1)$ 또는 $(3, i+1)$로 이동 가능하다. $(1 \leq i \leq N-1)$

현재 위치한 칸에서 다른 칸으로 이동할 때마다 저항력을 1ドル$ 소모하며, 도착한 칸 $(i. j)$에 해당하는 점수 $A_{ij}$를 얻는다. 단, [START]와 [GOAL]은 도착하더라도 별도의 점수를 주지 않는다.

[START]와 [GOAL]를 제외한 각 칸은 일반 스테이지, 정예 스테이지, 그리고 최정예 스테이지 중 하나로 구성되어 있다. 중앙 라인은 모두 일반 스테이지로 구성되어 있으며, 위 라인과 아래 라인은 정예 스테이지 또는 최정예 스테이지로 구성되어 있다. 각 스테이지를 지날 때마다 아래와 같은 효과를 받는다:

• 일반 스테이지: 저항력 1ドル$을 회복한다.
• 정예 스테이지: 아무런 변화가 없다.
• 최정예 스테이지: 추가로 저항력 1ドル$을 소모한다.

만약 이동 직전에 저항력이 0ドル$ 이하라면 더 이상 앞으로 나아갈 수 없어 아쉽지만 탐사를 중단해야 한다.

메린이 멘보롱은 [START]에서 출발하여 [GOAL]에 도착했을 때의 최대 점수를 얻어 가능한 많은 보상을 받고 싶다! 그를 위해 [GOAL]에 도착했을 때의 최대 점수를 대신 구해주자!

입력

첫 번째 줄에 초기 $N$과 초기 저항력 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 300,000円;$ 1ドル \leq K \leq 10^9)$

두 번째 줄에 $N$번에 걸쳐 위치 $(1, i)$ 노드의 정예/최정예 여부가 공백으로 구분되어 주어진다. 1ドル$은 정예 스테이지, 2ドル$는 최정예 스테이지를 의미한다.

세 번째 줄에 $N$번에 걸쳐 위치 $(3, i)$ 노드의 정예/최정예 여부가 공백으로 구분되어 주어진다. 1ドル$은 정예 스테이지, 2ドル$는 최정예 스테이지를 의미한다.

네 번째 줄에 $N$번에 걸쳐 $A_{1i}$ 가 공백으로 구분되어 주어진다. $(1 \leq A_{1i} \leq 10^9)$

다섯 번째 줄에 $N+1$번에 걸쳐 $A_{2i}$ 가 공백으로 구분되어 주어진다. $(1 \leq A_{2i} \leq 10^9)$

여섯 번째 줄에 $N$번에 걸쳐 $A_{3i}$ 가 공백으로 구분되어 주어진다. $(1 \leq A_{3i} \leq 10^9)$

입력으로 주어지는 모든 수는 정수이며, 항상 [START]에서 [GOAL]로 도달할 수 있는 경로가 존재하는 입력으로 주어진다.

출력

[START]에서 출발해서 [GOAL]에 도착했을 때 얻을 수 있는 최대 점수를 출력한다.

제한

힌트