ByteCity tiene un metro cuyos trenes consisten de un solo vagón y hay una sola fila de ~L~ asientos en ella. Si hay ~N~ pasajeros en el vagón, numerados de ~0~ a ~N-1~, cada pasajero recibe una cierta cantidad de placer como sigue:

• Si un pasajero está de pie, obtiene un placer igual a ~0~;
• De lo contrario, el pasajero obtiene ~A[i]~ placer de estar sentado y ~B[i]~ placer adicional por cada asiento vacío entre él y un pasajero vecino o entre él y el final de la fila de asientos.

Por ejemplo, tengamos ~3~ pasajeros en el vagón, numerados ~0, 1~ y ~2~, y ~A[0]=5~, ~B[0]=2~, ~A[1]=10~, ~B[1]=1~, ~A[2]=1~, ~B[2]=1~. Deje el número de asientos ~L=6~ y considere a los pasajeros sentados en el siguiente esquema: _ 0 _ _ 1 _ ("_" significa un asiento vacío). El pasajero 2 está de pie.

En este caso:

• El pasajero ~0~ obtiene placer ~5~, porque está sentado + placer ~6~, debido a los asientos vacíos (~1~ a la izquierda y ~2~ a la derecha). Eso es proporciona un placer total de ~11~.
• El pasajero ~1~ obtiene placer ~10~, porque está sentado + placer ~3~, debido a los asientos vacíos (~2~ a la izquierda y ~1~ a la derecha). Total de ~13~.
• El pasajero ~2~ obtiene placer ~0~, porque está de pie.

El placer total de todos los pasajeros es igual a ~24~.

Escriba un programa, que, dado el número de pasajeros ~N~, el número de asientos ~L~, y las características del placer de cada pasajero, determine el máximo placer total posible para cualquier número de pasajeros sentados entre ~1~ y ~N~.

Entrada

La primera línea de la entrada estándar contiene dos enteros, ~N~ y ~L~, el número de pasajeros y el numero de asientos. Cada una de las siguientes ~N~ líneas contiene dos enteros no negativos: las características \(А[i]\) y ~B[i]~ para el pasajero con índice ~i~.

Salida

Imprima ~N~ líneas, cuya ~K^{th}~ contiene un solo número, el máximo placer total que el pasajero puede obtener si hay exactamente ~K~ de ellos sentados. (Para ~K>L~ imprima ~0~, porque no hay configuraciones válidas de ~K~ pasajeros en los ~L~ asientos).

Restricciones

• ~1 \leq N \leq 100000~
• ~1 \leq L \leq 200000~
• ~0 < A[i], B[i] < 10^9~

Subtareas

• Subtarea 1 (20 puntos): ~1 \leq N \leq 200~
• Subtarea 2 (30 puntos): ~1 \leq N \leq 5000~
• Subtarea 3 (50 puntos): no hay restricciones adicionales para los otros casos de prueba.

Ejemplo # 1 de Entrada

3 2
1 2
3 4
5 6

Ejemplo # 1 de Salida

11
8
0

Explicacion del Ejemplo 1: Para К = 2 la configuración óptima es: ~1,2~. Entonces el pasajero ~1~ obtiene placer ~3~, por estar sentado y ~0*4~, porque no hay asientos vacíos entre él y los otros pasajeros. Del mismo modo, el pasajero ~2~ obtiene placer ~5 + 0 * 6~. El pasajero ~0~ está de pie, por lo que obtiene placer ~0~. En total: ~0 + (3 + 0 * 4) + (5 + 0 * 6) = 8~.

Ejemplo # 2 de Entrada

3 3
1 2
3 4
5 100

Ejemplo # 2 de Salida

205
112
9

*Explicacion del Ejemplo 2: Para \(К=1\) la configuración óptima es: 2, _, _. El placer total es: ~0 + 0 + (5 + 2 100) = 205~.