최소-플러스 합성곱 (볼록 및 볼록)

정수 수열 $a_0, a_1, ..., a_{N - 1}$와 $b_0, b_1, ..., b_{M - 1}$가 주어진다. 여기서 $a$와 $b$는 볼록하다. 다음과 같이 정의되는 정수 수열 $c_0, c_1, ..., c_{(N - 1) + (M - 1)}$을 계산한다:

$c_k = \min_{i+j=k} (a_i+b_j)$

제약 조건

• $1 \leq N, M \leq 524288$
• $0 \leq a_i, b_i \leq 1000000000$
• $a$는 볼록하다. 즉, $0\leq i < N - 2$에 대해 $a_{i+1}-a_i\leq a_{i+2}-a_{i+1}$가 성립한다.
• $b$는 볼록하다. 즉, $0\leq i < M - 2$에 대해 $b_{i+1}-b_i\leq b_{i+2}-b_{i+1}$가 성립한다.

$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$

$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$