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

Poveste şi cerinţă...

Se dă o secvenţă de <tex>n</tex> întregi pozitivi <tex>A_1, A_2, \ldots, A_n</tex>, care se împarte în <tex>k \leq n</tex> subsecvenţe disjuncte <tex>L_1, L_2, \ldots, L_k</tex> care concatenate dau secvenţa iniţială.
 
<tex>L_1 = A_1, \ldots, A_{i_1 - 1} \quad L_2 = A_{i_1}, \ldots, A_{i_2 - 1} \quad \ldots \quad L_k = A_{i_{k-1}}, \ldots, A_n</tex>
 
Se consideră sumele întregilor subsecvenţelor <tex>L_1, L_2, \ldots, L_k</tex>:
 
<tex>S_1 = A_1 + \ldots + A_{i_1 - 1} \quad S_2 = A_{i_1} + \ldots + A_{i_2 - 1} \quad \ldots \quad S_k = A_{i_{k-1}} + \ldots + A_n</tex>
 
Scrieţi un program care să împartă secvenţa de <tex>n</tex> numere în <tex>k</tex> subsecvenţe astfel ca **valoarea maximă** a unei sume <tex>S_j</tex>, (<tex>1 \leq j \leq k</tex>) **să fie minimă** (adică <tex>Rezultat = \min \max\limits_{j=1..k} S_j</tex> dintre toate împărţirile posibile).

h2. Date de intrare

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

Fişierul de intrare $sume3.in$ conţine mai multe exemple de test. Un exemplu are pe prima linie doi întregi <tex>n, k</tex> separaţi de un spaţiu determinând numărul <tex>n</tex> al întregilor secvenţei şi numărul <tex>k</tex> al subsecvenţelor. Pe linia următoare se dau cei <tex>n</tex> întregi <tex>A_i</tex> separaţi de un spaţiu. Fişierul se termină cu o linie conţinând un **0**.

h2. Date de ieşire

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

Fişierul de ieşire $sume3.out$ conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de **':'** şi de **cea mai mică valoare maximă a sumei unei subsecvenţe** posibil a fi obţinută la o împărţire a secvenţei date.

h2. Restricţii

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

* <tex>1 \leq k \leq n \leq 500</tex>
* <tex>1 \leq A_i \leq 10^6, \forall i \in \lbrace 1, \ldots, n \rbrace</tex>

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

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

| 5 3
  1 2 3 4 5
  3 2
  4 78 9
  0
| 1:6
  2:82

|

h3. Explicaţie
 
...

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