Glotonería
Tres-Veltör participará en un concurso de comer. Los equipos tienen miembros que competirán en el concurso y el equipo de Tres-Veltör consiste de miembros numerados de hasta desde el mas joven hasta el mas viejo. El coeficiente de consumo del miembro es .
En el concurso comidas numeradas de hasta serán presentadas y la dificultad de la comida es . Los detalles del concurso son:
- Un equipo debe asignar un miembro a cada comida y el mismo miembro no puede estar asignado a múltiples comidas.
- Tomará segundos para un miembro finalizar la comida donde es el coeficiente de consumo del miembro e es la dificultad del plato.
- El puntaje de un equipo es el mayor tiempo que le tome a un miembro individual terminar su comida.
Antes del concurso el equipo de Tres-Veltör decidió entrenar. En una sesión de entrenamiento un miembro puede reducir su coeficiente de consumo por , mientras que este no sea . Además, por razones financieras los miembros pueden hacer a lo mas sesiones de entrenamiento en total.
¿Cuál es el mínimo puntaje posible que el equipo puede lograr si entrenan y se reparten los platos de forma óptima?
Límites:
Entrada:
La primera línea de entrada contiene dos enteros y .
La segunda línea números. El i-ésimo número es igual a .
La tercera línea números. El i-ésimo número es igual a .
Salida:
Imprime el mínimo puntaje posible que el equipo puede lograr si entrenan y se reparten los platos de forma óptima.
Entrada de ejemplo 1:
3 5
4 2 1
2 3 1
Salida de ejemplo 1:
2
Ellos pueden alcanzar el puntaje de de la siguiente forma:
Miembro hace sesiones de entrenamiento y come la comida en segundos
Miembro hace sesión de entrenamiento y come la comida en segundo
Miembro hace sesiones de entrenamiento y come la comida en segundos
No pueden alcanzar un puntaje menor que , asi que la respuesta es
Entrada de ejemplo 2:
3 8
4 2 1
2 3 1
Salida de ejemplo 2:
0
El equipo de Tres-Veltör puede escoger no hacer ningún entrenamiento
Entrada de ejemplo 3:
11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2
Salida de ejemplo 3:
12
Comments