Комп'ютери
Кожен любить комп'ютери, але придбання нового завжди є фінансовим викликом. На щастя, існує зручний спосіб впоратися з цим. Ви можете замінити свій комп'ютер і отримати абсолютно новий, що дозволяє заощадити на витратах на обслуговування. Звісно, за кожен новий комп'ютер потрібно сплатити фіксовану вартість.
Припустимо, ви розглядаєте період у n років, протягом якого хочете мати комп'ютер. Якщо ви купуєте новий комп'ютер у році y, де 1<=y<=n, то повинні сплатити фіксовану вартість c у році y, а також витрати на обслуговування m(y,z) кожного року, коли володієте цим комп'ютером, починаючи з року y до року z, де z<=n, коли ви плануєте - зрештою - купити інший комп'ютер.
Напишіть програму, яка обчислює мінімальну вартість володіння комп'ютером протягом n-річного періоду.
Вхідні дані
Вхідні дані програми зчитуються з текстового файлу. Кожен набір даних у файлі відповідає певному набору витрат. Набір даних починається з вартості c для отримання нового комп'ютера. Далі йде кількість n років та витрати на обслуговування m(y,z), де y=1..n, z=y..n. Програма виводить мінімальну вартість володіння комп'ютером протягом n-річного періоду.
Пробіли можуть вільно зустрічатися у вхідних даних. Вхідні дані є коректними і завершуються кінцем файлу.
Вихідні дані
Для кожного набору даних програма виводить результат на стандартний вихід з початку рядка.