순차 제조

어떤 제조 공정은 서로 다른 $N$대의 기계로 이루어져 있다. 원재료는 이 기계들을 순서대로 거쳐 완제품이 된다. $i$번째 기계는 입력된 제품 하나를 처리하는 데 $T_i$초가 걸린다.

제품은 첫 번째 기계에 들어가는 순간부터 자동으로 시스템을 따라 이동한다. 시간 여유를 주기 위해 각 기계 $i$에는 입력 영역이 있어, 그 기계의 처리를 기다리는 제품을 $K_i$개까지 보관할 수 있다. 기계 $i$가 제품 처리를 마치면, 다음 기계 $i + 1$이 비어 있을 때 바로 넘긴다. 비어 있지 않으면 기계 $i + 1$의 입력 영역에서 그 기계가 비기를 기다린다. 기계 $i + 1$이 사용 중이고 입력 영역이 가득 찬 상태에서 기계 $i$가 제품 처리를 마치면 시스템이 중단된다. 기계 $i$와 $i + 1$이 같은 시각에 각각 제품 처리를 마치면, 기계 $i$의 제품은 먼저 기계 $i + 1$의 입력 영역을 거칠 필요가 없다.

방금 대량 주문을 받았다. 원재료는 무한히 있으며, 제품을 기계 1에 넣는 시각은 직접 정할 수 있다. 시스템이 멈추지 않게 하면서 이 제품들을 얼마나 빨리 다 만들 수 있을까?

첫 줄에 기계의 수 $N$ ($1 \le N \le 1\,000$)과 만들어야 할 제품의 수 $P$ ($1 \le P \le 10^9$)가 정수로 주어진다.

다음 줄에는 각 기계의 처리 시간 $T_1, \dots, T_N$ ($1 \le T_i \le 10^9$)이 주어진다. 모두 정수이다.

그다음 줄에는 입력 영역의 크기 $K_2, \dots, K_N$ ($1 \le K_i \le 10^9$)이 주어진다. 모두 정수이다. 첫 번째 기계에는 입력 영역이 없다.

제품 $P$개를 모두 만드는 데 걸리는 시간(초)을 출력한다. 마지막 제품이 마지막 기계에서 처리를 마치는 시점을 제조 완료로 본다.