h3(#problema-1). Problema 1: 'Be a Smart Raftsman':http://acm.sgu.ru/problem.php?contest=0&problem=475 (SGU)
bq. Sunteţi membri ai unui echipaj de rafting care constă din $N ≤ 10$ participanţi. Puteţi naviga pe râu, şi scopul vostru este să treceţi de $M ≤ 1000$ curenţi consecutivi şi să ajungi de la punctul de început la punctul de sfârşit în timp minim. Cel de-al $i$-lea curent se caracterizează prin greutatea critică $c{~i~}$, iar al $j$-lea participant este caracterizat greutatea sa $w{~j~}$. În cazul în care pluta trece prin al $i$-lea curent cu oameni la bord cu greutatea totală mai mare de $c{~i~}$, ea se răstoarnă. Această parte a rafting-ului este cea mai interesantă, dar este nevoie de timp suplimentar pentru a te urca pe plută după răsturnare. Deci, uneori este mai bine să se urce un grup de oameni cu greutate totală care nu depăşeşte greutatea critică a plutei, în timp ce restul parcurg distanţa pe jos.

Mai formal, vom considera $M + 1$ puncte $P{~0~}, P{~1~} ,..., P{~M~}$, în cazul în care $P{~0~}$ este începutul şi $P{~M~}$ este punctul final. Fiecare dintre punctele intermediare $P{~i~} (1 ≤ i ≤ M-1)$ este situat între $i$-lea şi $(i + 1)$-lea curent. Dacă pluta se răstoarnă, sunt necesare $D{~i~}$ minute pentru a ajunge de la $P{~i-1~}$ la $P{~i~}$, altfel sunt necesare $d{~i~}$ minute. Cel de-al $j$-lea participant poate merge pe jos de la $P{~i-1~}$ la $P{~i~}$ în $t{~j~}$ minute, iar pentru a se urca sau a coborî din plută are nevoie de $s{~j~}$ minute. Înainte de fiecare curent, grupul vostru este împărţit în două părţi. Prima parte trece prin curent cu pluta, iar a doua parte merge pe mal spre următorul punct. Cei care ajung primii îi aşteaptă pe toţi ceilalţi. Apoi, unii participanţi care sunt pe plută se pot da jos, în timp ce alţi participanti care sunt pe mal se pot urca pe plută. Această activitate începe când ajung pluta şi toţi cei de pe mal la punctul stabilit. Timpul total necesar pentru această acţiune este egal cu suma valorilor $s{~j~}$ pentru toate persoanele care schimbă locul (mai exact, persoanele urcă sau coboară pe rând). Nimeni nu poate începe deplasarea la următorul punct, până când nu s-au mutat toţi membrii.

Mai formal, vom considera $M + 1$ puncte $P{~0~}, P{~1~} ,..., P{~M~}$, în cazul în care $P{~0~}$ este începutul şi $P{~M~}$ este punctul final. Fiecare dintre punctele intermediare $P{~i~} (1 ≤ i ≤ M-1)$ este situat între $i$-lea şi $(i + 1)$-lea curent. Dacă pluta se răstoarnă, sunt necesare $D{~i~}$ minute pentru a ajunge de la $P{~i-1~}$ la $P{~i~}$, altfel sunt necesare $d{~i~}$ minute. Cel de-al $j$-lea participant poate merge pe jos de la $P{~i-1~}$ la $P{~i~}$ în $t{~j~}$ minute, iar pentru a se urca sau a coborî din plută are nevoie de $s{~j~}$ minute. Înainte de fiecare curent, grupul vostru este împărţit în două părţi. Prima parte trece prin curent cu pluta, iar a doua parte merge pe mal spre următorul punct. Cei care ajung primii îi aşteaptă pe toţi ceilalţi. Apoi, unii participanţi care sunt pe plută se pot da jos, în timp ce alţi participanti care sunt pe mal se pot urca pe plută. Această activitate începe când ajung pluta şi toţi cei de pe mal la punctul stabilit. Timpul total necesar pentru această acţiune este egal cu suma valorilor $s{~j~}$ pentru toate persoanele care schimbă locul (persoanele urcă şi coboară pe rând). Nimeni nu poate începe deplasarea la următorul punct, până când nu s-au mutat toţi membrii.

începeţi de la punctul de $P{~0~}$ cu tot grupul pe mal şi trebuie să terminaţi la punctul $P{~M~}$ cu toţi participanţii şi pluta pe mal. Nu aveţi voie să părăsiţi pluta la început sau într-un un punct intermediar şi să mergeţi pe jos spre linia de sosire fără ea. Aveţi posibilitatea să urcaţi tot grupul de salvare în plută, dar nu puteţi lăsa pluta goală în timpul călătoriei printr-un curent.
Sarcina voastră este să calculaţi timpul minim necesar pentru a ajunge la linia de sosire.