31412번 - 군수품 창고 정리

문제

군수품 창고에 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円)$

출력

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

제한

힌트