h3(#problema-3). Problema 3: 'Trans':problema/trans (ONI 2004)

bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.

bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea.

Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.
Restricţii: $1 ≤ N ≤ 16 000$, $1 ≤ Q ≤ 100$, $1 ≤ K{~i~} ≤ N$.