Anteproyecto de los presupuestos
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