Ngưỡng Điều Chỉnh Chung

Cho hai dãy nguyên dương $a$ và $b$ . Một thao tác tăng hoặc giảm một phần tử đúng $1$ . Cần biến đổi sao cho $min (a) \geq max (b)$ . Hãy tìm số thao tác ít nhất.

Input

Dòng đầu $n$ $m$ ; dòng hai có $a$ , dòng ba có $b$ .

Output

In số thao tác ít nhất.

Constraints

$1 \leq n, m \leq 1 0^{5}$ .
$1 \leq a_{i}, b_{j} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50$ điểm): $n, m \leq 1000$ , giá trị $\leq 1 0^{4}$ .
Subtask $2$ ( $50$ điểm): đầy đủ.

Example

Test 1

Input

3 2
1 4 9
5 8

Output

Giải thích: Với ngưỡng $4$ , nâng $1$ tốn $3$ , hạ $5, 8$ tốn $1 + 4$ ; tổng $8$ . Ngưỡng $5$ cũng tốn $8$ , các ngưỡng khác không tốt hơn.

Lời giải tóm tắt

Ý tưởng: Cố định ngưỡng nguyên h, phương án rẻ nhất có chi phí C(h)=Σmax(0,h-a_i)+Σmax(0,b_j-h). Mỗi hạng là hinge lồi nên tổng lồi.
Ý tưởng: Tam phân nguyên trên [1,10^9], rồi vét đoạn còn tối đa chín giá trị. Tính lồi bảo đảm thu hẹp không bỏ hết đáy; vét cuối trả đúng min. Độ phức tạp O((n+m)log10^9), bộ nhớ O(n+m).