اليوم ممطر! أبقار Farmer John وعددها $N$ ($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