За билетами в цирк выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем, когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

Однако для борьбы со перекупщиками кассир продавала не более 3 билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов—Bi секунд, трех билетов—Ci секунд.

Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (т. е. билетов, которые никому не нужны).

Формат входных данных
Во входном файле записано сначала число N —количество покупателей в очереди (1 <N < 5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

Формат выходных данных
В выходной файл выведите одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.

Попробуем найти решение задачи, постепенно увеличивая размер очереди. Пусть у нас в очереди стоит всего один человек. Поскольку каждому человеку нужен один и только один билет (даже если 2 или 3 билета купить быстрее), то ответом задачи будет число A1.

Теперь перейдем к очереди из 2 человек. Они могут купить билеты раздельно, тогда время покупки составит A1 + A2. Кроме того, они могут объединиться и купить билеты вместе, причем купить два билета по условию задачи может только первый человек. Из двух возможностей выбираем такую, которая займет меньше времени, и запоминаем это время в элементе D[2] специального массива. Таким образом, D[2] — минимальное время покупки билетов очередью из 2 первых человек.

Добавим в очередь третьего человека. Какие варианты есть у нас? Если третий человек покупает билет самостоятельно, то первые два, очевидно, не зависят от него. Тогда (внимание!) мы уже решили эту задачу! Мы только что нашли минимальное время покупки билетов для очереди из двух человек, оно хранится в D[2]. Общее время покупки в этом случае составит D[2] + A3. Допустим, второй и третий человек решат купить билеты вместе. Ответом в этом случае будет B2 + A1 (два билета покупает второй человек, и первый человек покупает билет самостоятельно). Наконец, договориться смогут и все три человека. Тогда они купят билеты за C1 — именно столько времени займет покупка трех билетов первым стоящим в очереди человеком. Запишем лучший вариант в D[3] — это будет минимальное время покупки билетов очередью из 3 первых человек.

Рассмотрим все вышесказанное на примере из условия.

Заполним массив D начальными значениями, D[1] = A1, остальные элементы пока неизвестны.

Переходим к выяснению значения D[2]. Имеем, что время покупки билетов раздельно составит A1 + A2 = 5 + 2 = 7, а при покупке вместе —10.
Итак

Добавляем в очередь третьего человека. Если он покупает билет отдельно, то общее время равно: D[2] + A3 = 7 + 5 = 12.

Если второй и третий договариваются между собой, то общее время будет: D[1] + B2 = 5 + 10 = 15. Наконец, в случае совместной покупки билетов тремя любителями мюзиклов, им удастся это сделать за время C1 = 15. Разумеется, выбираем самый быстрый вариант, и в данном случае D[3] = min(12, 15, 15) = 12.

Дальше будем действовать совершенно аналогично. Добавляем к очереди четвертого человека. Выпишем формулу для D[4].

Итак, D[4] = min(12 + 20, 7 + 5, 5 + 15) = min(32, 12, 20) = 12.

D[i] = min(D[i − 1] + Ai, D[i − 2] + Bi−1, D[i − 3] + Ci−2).
Ответом к задаче будет служить элемент массива D[N]. В нашем случае это D[5].

Дорешаем наш пример: D[5] = min(12 + 20, 12 + 20, 7 + 5) = min(32, 32, 12) = 12

Принцип, используемый при решении этой задачи, называется динамическим программированием. В данном случае мы решаем полную задачу, постепенно увеличивая ее размерность и используя решения более маленьких «подзадач».

Полное решение задачи на языке Паскаль.
const
MaxN = 5000;
var
n : word; {число человек в очереди}
a, b, c : array [0 .. MaxN] of integer;
d : array [0 .. MaxN] of longint;
i : integer;
function min(a,b : longint) : longint;
begin
if a<b then min:=a else min:=b;
end;
begin
assign(input, ’b.in’);
reset(input);
assign(output, ’b.out’);
rewrite(output);
readln(n);
for i := 1 to n do
read(a[i], b[i], c[i]);
d[0] := 0;
d[1] := a[1];
d[2] := min(a[1]+a[2], b[1]);
for i := 3 to n do
d[i] := min(d[i-1]+a[i], min(d[i-2]+b[i-1], d[i-3]+c[i-2]));
writeln(d[n]);
close(input);
close(output);
end.