파이 가게

당신은 동네에서 가장 맛있는 파이를 굽는 제과점의 주인이다. 매일 $n$명의 손님이 가게에 오며, $i$번째 손님은 시각 $t_i$에 도착한다. 파이는 시각 0부터 굽기 시작할 수 있다. 손님은 도착한 뒤 좋아하는 파이가 오븐에서 나올 때까지 기다린다. 식은 파이를 좋아하는 사람은 없으므로, 손님은 기다릴 수 있지만 파이는 손님을 기다리며 식어서는 안 된다.

오븐은 한 번에 파이 한 개만 구울 수 있고, 굽는 도중에는 문을 열 수 없다. 파이 하나를 굽는 데 걸리는 시간은 항상 같다. 각 손님의 도착 시각을 미리 알고 있으므로, 손님들의 총 대기 시간이 최소가 되도록 굽는 순서를 정한다.

현재 오븐이 낡아서 새 오븐을 살 때가 되었다. 관심 있는 오븐 모델이 $m$개 있으며, $i$번째 모델로 파이 한 개를 굽는 데 $d_i$가 걸린다. 가장 빠른 오븐을 원하지만 살 여유가 있는지는 확실하지 않다. 각 모델에 대해, 그 오븐을 사고 굽는 순서를 최적으로 정했을 때 손님들이 기다리는 총 시간을 구한다.

첫 번째 줄에는 두 정수 $n$과 $m$이 주어진다 ($1 \leq n, m \leq 200000$). 두 번째 줄에는 $n$개의 정수 $t_1, t_2, \ldots, t_n$이 주어진다 ($0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^{12}$). 같은 시각에 여러 손님이 올 수 있다. 세 번째 줄에는 $m$개의 정수 $d_1, d_2, \ldots, d_m$이 주어진다 ($1 \leq d_i \leq 10^6$).

정확히 $m$줄을 출력한다. $i$번째 줄에는 $i$번째 오븐 모델을 사용하고 굽는 순서를 최적으로 정했을 때의 손님 총 대기 시간의 최솟값을 한 정수로 출력한다.