Задача . E. Собираем строку

Вам очень нужно собрать некоторую строку t. Для этого Вы заранее приготовили n некоторых строк s₁, s₂, ..., s_n. Чтобы собрать строку t, Вам разрешатся выполнить ровно |t| (|t| — длина строки t) операций с этими строками. Каждая операция имеет следующий вид:

1. выбрать любую непустую строку из строк s₁, s₂, ..., s_n;
2. выбрать произвольный символ выбранной строки и записать его на листок бумаги;
3. удалить выбранный символ из выбранной строки.

Заметьте, что после применения описанной операции общее количество символов в строках s₁, s₂, ..., s_n уменьшится на 1. Считается, что вы собрали строку t, если символы, записанные на листок бумаги, в порядке применения операций образуют строку t.

Однако есть и другие ограничения. Для каждой строки s_i Вам известно число a_i — максимальное количество символов, которое разрешается удалить из строки s_i. Также известно, что каждая операция, в результате которой из строки s_i удаляется символ, имеет цену i рублей. То есть, операция над строкой s₁ самая дешевая (она стоит 1 рубль), а операция над строкой s_n — самая дорогая (она стоит n рублей).

Вам нужно посчитать, какое наименьшее количество денег (в рублях) потребуется, чтобы собрать строку t по описанным правилам. Считайте, что стоимость сборки строки t — это сумма цен использованных Вами операций.