Ir al contenido (saltar navegación)

Anteproyecto de los presupuestos

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB
Preparando el presupuesto

El gobierno está preparando los presupuestos del año próximo. Una de las partidas estará destinada a las prestaciones por desempleo. La cuantía reservada para ese concepto ya está decidida y también el mecanismo de reparto, que será el mismo que el año anterior. En concreto, a cada solicitante se le dará la cantidad equivalente a su último sueldo. Eso sí, si su sueldo supera un cierto umbral U entonces la cantidad percibida será exactamente U. Al fin y al cabo, no queremos que con las arcas públicas se paguen los altísimos sueldos de estrellas de fútbol en paro.

Lo único que nos queda por decidir es cuál es el umbral U que elegiremos para que, según la estimación de prestaciones que tendremos que cubrir, no nos quedemos sin dinero. Y en caso de que haya varias posibilidades cogeremos aquel umbral que haga que gastemos lo máximo posible. Si aún así hay varias posibilidades, elegiremos el umbral más bajo posible.

Entrada

La entrada está formada por distintos casos de prueba, cada uno ocupando dos líneas.

La primera línea de cada caso comienza con el dinero disponible para pagar las prestaciones por desempleo (hasta 109); a continuación aparece el número de receptores n de esas prestaciones (no más de 10.000). La segunda línea contiene n números entre 0 y 109 con el último sueldo de cada uno.

Salida

Por cada caso de prueba se escribirá el umbral U que hay que fijar para que se pueda pagar a todos según la regla de reparto. En caso de haber varias posibilidades, se escribirá aquel que gaste más presupuesto.

Entrada de ejemplo

1000 4
400 500 300 400
1000 4
400 500 100 100
1000 4
100 100 100 100

Salida de ejemplo

250
400
100