== include(page="template/taskheader" task_id="cubeon") ==

Poveste şi cerinţă...

Cei $K$ (cu $K$ ≥ $1$) membrii ai Clubului Light Cubing doresc să se mute pe Cube Street. Pe această stradă, sunt $N$ (cu $1$ ≤ $N$) clădiri adiacente, fiecare cu o anumită lăţime. Cei $K$ membrii vor cumpara fiecare secvenţe consecutive de clădiri (care sunt disjuncte doua cate doua), le vor distruge şi vor construi o casa pe pământ din acele clădiri. Din motive evidente, membrii iubesc cu adevărat cuburile şi, astfel, vor construi fiecare casă în formă de cub, a cărei lungime a marginii este egală cu lăţimea totală a clădirilor care au fost
demolat1 pentru a face loc pentru acea casa. De asemenea, nu vor să trăiască lângă cei care nu împărtăşesc dragostea lor de cuburi, deci doresc ca fiecare clădire să fie cumpărată de un singur membru al clubului. În timp ce membrii nu sunt săraci, nu sunt făcuţi din bani (ca, desigur, nu este vorba despre cubi). Aşa că ar dori ştiţi ce costuri totale minime pot fi plătite pentru a construi clădirile. Reţineţi că costul pentru a construi o clădire a cărei margine este $x$ unităţi lungime este $x^3^$.

h2. Date de intrare

Fişierul de intrare $cubeon.in$ ...

Fişierul de intrare $cubeon.in$ contine pe prima linie $T$, numărul de teste.
Fiecare test va conţine două linii. Prima linie va conţine $N$ şi $K$. A doua linie va conţine $N$ numere întregi ne-negative a căror sumă nu va depăşi $1.000.000$, lăţimile clădirilor $N$.

h2. Date de ieşire

În fişierul de ieşire $cubeon.out$ ...

În fişierul de ieşire $cubeon.out$ se vor afla răspunsurile pentru fiecare test în ordine.
Pentru fiecare test, obţineţi costul total minim.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1$ ≤ $T$ ≤ $20$
* $1$ ≤ $N * K$ ≤ $1.000.000$

h2. Exemplu
table(example). |_. cubeon.in |_. cubeon.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
8 3
1 2 1 3 1 4 3 2
| 593

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="cubeon") ==