¡Hoy es un día lluvioso! A las ~N~ ~(1 \leq N \leq 5,000)~ vacas del Granjero Juan, numeradas ~1..N~, no les gusta mojarse. Las vacas están en pesebreras sin techo organizadas en una línea numérica. Las pesebreras abarcan ~N~ coordenadas ~X~ de ~1~ a ~M~ ~(1 \leq M \leq 100,000)~. La vaca ~i~ está en una pesebrera en la coordenada ~X_i~ ~(1 \leq X_i \leq M)~. Ningún par de vacas comparte pesebrera.

Para proteger a las vacas de la lluvia, el Granjero Juan quiere comprarles paraguas. Un paraguas que abarca las coordenadas de ~X_i~ a ~X_j~ ~(X_i \leq X_j)~ tiene un ancho de ~X_j - X_i + 1~. Cuesta ~C_W~ ~(1 \leq C_W \leq 1,000,000)~ comprar un paraguas de ancho W. Paraguas más grandes no cuestan necesariamente más que paraguas más pequeños.

Ayude al Granjero Juan a encontrar el mínimo costo para comprar un conjunto de paraguas que protegerá a cada vaca de la lluvia. Note que en el conjunto de paraguas en una solución óptima pueden haber paraguas que se sobrelapen.

Entrada

• Línea 1: Dos enteros separados por un espacio: ~N~ y ~M~.
• Líneas 2..N+1: La línea ~i+1~ contiene un solo entero: ~X_i~.
• Líneas N+2..N+M+1: La línea ~N+j+1~ contiene un solo entero: ~C_j~.

Salida

• Línea 1: Un solo entero que es el mínimo costo necesario para compra paraguas que cubran a todas las vacas.

Ejemplo de Entrada

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

Detalles de la Entrada: Hay 12 pesebreras y las pesebreras ~1, 2, 4, 8, 11~ y ~12~ tienen vacas. Un paraguas que cubre una pesebrera cuesta 2, un paraguas que cubre dos pesebreras cuesta 3, y así sucesivamente.

Ejemplo de Salida

9

Detalles de la Salida: Comprando un paraguas de tamaño 4, un paraguas de tamaño 1 y un paraguas de tamaño 2, es posible cubrir todas las vacas a un costo de ~4+2+3=9~:

PPPPPPPPPP           P        PPPP 
V  V     V           V        V  V 
|--|--|--|--|--|--|--|--|--|--|--| 
1  2  3  4  5  6  7  8  9  10 11 12

~V~ representa una vaca y ~P~ representa una parte de un paraguas.

USACO 2011 December Contest, Silver Division Problem 3. Umbrellas for Cows.