היום גשום! $N$ הפרות של Farmer John ($1 \le N \le 5,000$), מספרים $1..N$, אינן אוהבות להירטב. תאים חסרי גג על ישר המספרים בקואורדינטות $X$ מ-1 עד $M$ ($1 \le M \le 100,000$). פרה $i$ ב-$X_{i}$ ($1 \le X_{i} \le M$), בלי שיתוף תא.

רוצה מטריות. מ-$X_{i}$ עד $X_{j}$ ($X_{i} \le X_{j}$) הרוחב $X_{j} - X_{i} + 1$. רוחב $W$ עולה $C_W$ ($1 \le C_{W} \le 1,000,000$). גדולה לא בהכרח יקרה יותר.

מצאו עלות מזערית לקבוצה המגינה על כולן. מטריות מיטביות עשויות לחפוף חלקית.

קלט

• שורה 1: השלמים $N$, $M$ ברווחים.
• שורות $2..N+1$: שורה $i+1$ מכילה שלם $X_{i}$.
• שורות $N+2..N+M+1$: שורה $N+j+1$ מכילה שלם $C_{j}$.

פלט

• שורה 1: עלות מזערית שלמה לכל הפרות.

דוגמאות

קלט 1

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

פלט 1

9

הערה

יש 12 תאים, תפוסים ב-1, 2, 4, 8, 11, 12. כיסוי תא אחד עולה 2, שניים 3, וכן הלאה.

אחת בכל רוחב 4, 1, 2 תכסה את כולן בעלות $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$ מציין פרה, $U$ חלק מטרייה.

מחבר הבעיה: Alex Chen, 2011