Tras volver de su dulce peregrinaje, Alicia difundió su experiencia con sus amigos de Myspace. Tanto les interesó que le propusieron a Alicia repetirlo el año siguiente junto a ellos. De esa manera, además, podrían todos conocerse en la realidad por primera vez. Así, pasa el tiempo, hasta que la fecha marcada para la realización de la ruta se acerca.

Es entonces cuando se dan cuenta de que, ahora que son varias personas, cada una de ellas con su mochila, tienen que buscar una forma de seleccionar y repartir los alimentos. Esta vez, tu misión consiste en calcular cuántos gramos de azúcar podrán llevarse en total, como máximo, si deciden de forma óptima.

No se dará el caso en el que Alicia tenga más de 3 amigos. Además, se asume que ninguno de ellos ha mentido sobre su edad, género, sexualidad, estudios, "body count" u orfandad.

Entrada

La primera línea contendrá dos enteros: ~n~ (~1 \le n \le 7 \cdot 10^{3}~), el número de alimentos con los que cuentan en total, y ~p~ (~1 \le p \le 4~), el número de personas que peregrinarán.

La segunda línea contendrá ~p~ enteros: ~m_{i}~ (~1 \le m_{i} \le 70~), el peso límite de la mochila de la ~i~-ésima persona (~1 \le i \le p~).

Las siguientes ~n~ líneas contendrán dos enteros: ~s_{j}~ (~1 \le s_{j} \le 70~), los gramos de azúcar en el ~j~-ésimo alimento, y ~w_{j}~ (~1 \le w_{j} \le 70~), el peso del ~j~-ésimo alimento (~1 \le j \le n~).

Por conveniencia, los pesos y los gramos de azúcar han sido divididos entre ~100~ con respecto a los del problema anterior. Además, se garantiza que ~n \cdot \prod_{i=1}^{p} (m_{i} + 1) \le 10^{8}~.

Salida

Se ha de imprimir un entero ~k~, los gramos de azúcar que podrán llevarse en total, como máximo.

Puntuación

• 50 puntos: ~n \le 11~
• 50 puntos: Sin restricciones.

Ejemplo 1

Entrada

4 1
12
7 9
4 5
4 4
1 4

Salida

8

Ejemplo 2

Entrada

6 4
2 4 8 16
1 1
2 3
3 4
5 7
8 14
13 18

Salida

17