Hôm nay mưa! $N$ bò của Farmer John ($1 \le N \le 5,000$), số $1..N$, không thích ướt. Chuồng không mái trên trục số có tọa độ $X$ từ 1 tới $M$ ($1 \le M \le 100,000$). Bò $i$ ở $X_{i}$ ($1 \le X_{i} \le M$), không hai bò chung chuồng.

Muốn mua ô. Từ $X_{i}$ tới $X_{j}$ ($X_{i} \le X_{j}$) rộng $X_{j} - X_{i} + 1$. Rộng $W$ giá $C_W$ ($1 \le C_{W} \le 1,000,000$). Ô lớn không nhất thiết đắt hơn.

Tìm giá nhỏ nhất của tập ô bảo vệ tất cả. Ô tối ưu có thể chồng lấn phần nào.

Dữ liệu vào

• Dòng 1: số nguyên $N$, $M$ cách bằng dấu cách.
• Dòng $2..N+1$: dòng $i+1$ chứa số nguyên $X_{i}$.
• Dòng $N+2..N+M+1$: dòng $N+j+1$ chứa số nguyên $C_{j}$.

Dữ liệu ra

• Dòng 1: số nguyên chi phí nhỏ nhất cho mọi bò.

Ví dụ

Dữ liệu vào 1

6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19

Dữ liệu ra 1

9

Ghi chú

Có 12 chuồng, bò ở 1, 2, 4, 8, 11, 12. Ô che một chuồng giá 2, hai giá 3 và tiếp tục.

Một ô mỗi độ rộng 4, 1, 2 che tất cả với giá $4+2+3=9$:

UUUUUUUUUU           U        UUUU
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

$C$ là bò, $U$ là phần ô.

Tác giả bài toán: Alex Chen, 2011