Fişierul intrare/ieşire:	cubeon.in, cubeon.out	Sursă	AGM 2019, runda nationala
Autor	Tamio-Vesa Nakajima	Adăugată de	Patrick Sava •xtreme77
Timp execuţie pe test	2.75 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cubeon

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³.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

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

Exemplu

Cum se trimit solutii?