Объединение блоков

Изделие изготавливают из n блоков, каждый из которых имеет два технологических параметра – m_i и k_i. Известно, что k_i=m_i+1, i=1, 2, …, n-1. При этом условии два последовательных блока i и i+1 можно объединять в один новый, который будет иметь технологические параметры - m_i и k_i+1, и на это потребуется m_i*k_i+1 технологических операций. Новый блок можно опять объединять с одним из соседних и так далее. Меняя порядок сборки блоков можно добиться уменьшения количества технологических операций.

Поясним это на примере трех блоков: 34 и 29, 29 и 4, 4 и 15. Если собрать вначале 2 и 3 блок, а затем присоединить собранное к первому, то потребуется 29*15+34*15=435+510=945 операций. Если собрать вначале блок из 1 и 2 исходных блоков, а затем присоединить 3 блок, то потребуется 34*4+34*15=136+510=646 операций.

Требуется написать программу, которая найдет минимальное число технологических операций для изготовления изделия.

Входные данные

Входной файл INPUT.TXT содержит в первой строке число n – количество блоков (1 ≤ n ≤ 100). Последующие n строк содержат пары чисел (разделенных пробелом) – технологические параметры блоков. Технологические параметры – целые неотрицательные числа, не превышающие 100.

Выходные данные

Выходной текстовый файл OUTPUT.TXT должен содержать одно число – минимальное число технологических операций.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]