Farmer John sufrió una terrible pérdida cuando cucarachas australianas gigantes comieron todo su heno, dejándolo sin nada para alimentar a las vacas. Enganchó su carro de capacidad $C$ $(1 \le C \le 50,000)$ unidades cúbicas y fue tranquilamente a casa de Farmer Don a buscar heno antes de que las vacas perdieran una comida.
Farmer Don vendía una gran variedad de $H$ $(1 \le H \le 5,000)$ pacas de heno, cada una con su volumen $(1 \le V_{i} \le C)$. Las pacas son algo flexibles y pueden meterse en los espacios más extraños del carro.
FJ evalúa cuidadosamente los volúmenes para averiguar la mayor cantidad de heno que puede comprar para sus vacas.
Dadas la restricción de volumen y la lista de pacas disponibles, ¿cuál es el mayor volumen de heno que FJ puede comprar? Por supuesto, no puede comprar pacas parciales. Cada línea después de la primera describe una paca que puede comprar.
Entrada
- Línea 1: dos enteros $C$ y $H$ separados por un espacio.
- Líneas $2,\ldots,H+1$: cada una describe el volumen de una paca $V_{i}$.
Salida
- Línea 1: un entero con el mayor volumen de heno que FJ puede comprar según la lista de pacas y las restricciones.
Ejemplos
Entrada 1
7 3
2
6
5Salida 1
7Nota
El carro admite 7 unidades de volumen; se ofrecen tres pacas de volúmenes 2, 6 y 5 unidades, respectivamente.
Comprar las dos pacas menores llena el carro.
Créditos del problema: Rob Kolstad (problema tradicional), 2008