군수품 창고 정리

군수품 창고에 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 군수품 박스가 번호 순서대로 일렬로 놓여 있다. $i$번 박스에는 $a_i$개의 군수품이 들어 있다. 창고 정리를 맡은 부대에는 $1$번부터 $M$번까지 번호가 매겨진 $M$개의 분대가 있고, $j$번 분대에는 $b_j$명의 병사가 소속되어 있다.

지휘관은 부관에게 다음 방법을 활용하라고 지시했다. 군수품 박스 $N$개를 번호가 연속한 박스로 이루어진 $M$개 이하의 그룹으로 나눈다. 그룹의 개수만큼 분대를 차출하고, 각 박스 그룹을 차출한 분대에 하나씩 맡긴다. 그 분대의 병사들이 박스 그룹의 군수품을 모두 정리한다. 각 박스 그룹에는 최소 1개의 군수품 박스가 포함되어야 한다.

부관은 분대의 병사들이 맡은 작업을 다른 사람에게 떠넘기지 않도록, 병사마다 정리할 군수품의 개수를 미리 배정하기로 했다. 공평하게 나누기 위해, 지휘관이 지시한 방법을 따르면서 가장 많은 군수품을 정리하는 병사의 몫을 최소로 만들려고 한다.

부관의 의도대로 각 병사가 정리할 군수품의 개수를 모두 배정했을 때, 가장 많은 군수품을 정리하는 병사가 정리하게 될 군수품의 개수를 구하라.

첫 번째 줄에 군수품 박스의 개수 $N$과 분대의 개수 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 500\,000$; $1 \leq M \leq \min(N, 7)$)

두 번째 줄에 각 박스에 들어 있는 군수품의 개수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. ($1 \leq a_i \leq 1\,000\,000$)

세 번째 줄에 각 분대의 병사 수 $b_1, b_2, \cdots, b_M$이 공백으로 구분되어 주어진다. ($1 \leq b_j \leq 1\,000\,000$)

가장 많은 군수품을 정리할 병사가 정리하게 될 군수품의 개수를 출력한다.