Repartiendo Caramelos

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
leo
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

Los niños en un círculo infantil han recibido un gran saco que contiene M caramelos. Se ha decidido que los caramelos se distribuyan entre los N niños.

Cada niño ha indicado el número de caramelos que quiere. Si a un niño no se le da la cantidad de caramelos que quiere, se enojará. De hecho, se enfurecerá más por cada caramelo que le falte. Algunos especulan que su enojo será igual al cuadrado del número de caramelos de los que se le priva. Por ejemplo, si Julito declara que quiere 32 caramelos pero recibe sólo 29, le faltarían 3 caramelos, por lo que su enojo sería igual a 9.

Desafortunadamente, hay una cantidad insuficiente de caramelos para satisfacer a todos los niños. Por lo tanto, los dulces deben ser distribuidos de tal manera que la suma de el enojo de los niños sea mínima.

ENTRADA

La primera línea contiene dos números enteros, M (1 \le M \le 2*10^9) y N (1 \le N \le 100 000). Las siguientes N líneas contienen números enteros (uno por línea) que representan los deseos de los niños. Todos esos números son estrictamente menores que 2*10^9, y su suma siempre excede M.

SALIDA

La primera y única línea de salida debe contener la suma mínima del enojo de los niños.

Entrada ejemplo

5 3
1
3
2

Salida ejemplo

1

Entrada ejemplo

10 4
4
5
2
3

Salida ejemplo

4

Comments


  • -10
    Primervirgen  commented on Jan. 1, 2020, 11:14 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 5
      aniervs  commented on Jan. 17, 2020, 3:43 a.m.

      Si te fijas, este problema es de una Croatian Open Competition in Informatics (COCI). Búscalo y ya tendrás solución, código y casos de prueba, creo q es del primer contest del 2011 o del 2010.