teddy online judge

65. Limocargas

Limite de tiempo : 1 seg.   Total runs : 104  Aceptados : 14

Cada limogochi pose una carga limocarga (algo equivalente a electrocarga) única en su género y es sabido que cuando dos limogochis se saludan, se libera una limocarga igual a la diferencia absoluta de sus limocargas. Esto es, si dos limogochis tienen cargas 5 y 7 entonces la carga liberada es | 5 - 7 | = | -2 | = 2. Los limogochis suelen migrar cada año para el ritual de saludos. Ellos se juntan en el lugar de siempre y cuando todos han llegado, cada limogochi comienzan a saludar a los demás, sin saludar mas de una vez a un mismo limogochi, hasta que cada par de limogochis se haya saludado mutuamente. Lamentablemente, este ritual genera demasiada limocargas en la atmósfera y resulta peligroso para la supervivencia de las otras especies del planeta. Por ello, se ha determinado capturar un limogochi de tal modo que minimize la cantidad total de limocargas.

Problema

Dada la cantidad de limogochis y sus cargas. Encontrar la suma mínima de limocargas que se puede generar en el ritual de saludos considerando que un limogochi fue capturado.

Entrada

En la primer línea esta un entero C que indica el numero de casos.En la primera línea de cada caso viene un único entero 0 < n < 30000 que especifica la cantidad de limogochis. En las segunda línea vienen n enteros -200000 < x1, x2, ... xi, ..., xn < 200000 separados por un espacio, donde xi representa la carga del limogochi enumerado con el índice i. Observa que el primer limogochi esta enumerado con el indice 1, el segundo con el 2, etcetera.

Salida

Un único entero que representa la suma mínima de limocargas que se puede generar por los limogochis considerando que uno de ellos fue capturado.

Ejemplo

1
6 
4 3 10 -6 2 -1

48

Repechaje (Facil). ANPA 2010