Лиса Ciel зашла в парк аттракционов. И вот, она в очереди на колесо обозрения. В очереди стоит n людей (хотя нет, скорее лис): мы будем считать, что первая лиса стоит в начале очереди, а n-ая лиса стоит в хвосте очереди.
Всего имеется k гондол, мы распределяем лис по гондолам следующим образом:
- Когда подплывает первая гондола, q1 лис переходят из начала очереди в подплывшую гондолу.
- Затем, когда подплывает вторая гондола, q2 лис из начала оставшейся очереди переходит в эту гондолу.
...
- Оставшиеся qk лис идут с последнюю (k-ую) гондолу.
Обратите внимание, что числа q1, q2, ..., qk должны быть положительные. Из условия следует, что 
и qi > 0.
Вы знаете как лисам не хочется задерживаться в гондолах с незнакомцами. Итак, Ваша задача — найти оптимальный способ размещения (то есть определить оптимальную последовательность q), чтобы угодить всем. Для каждой пары лис i и j задано значение uij, обозначающее степень незнакомости. Можете считать, что uij = uji для всех i, j (1 ≤ i, j ≤ n) и что uii = 0 для всех i (1 ≤ i ≤ n). Тогда значение незнакомости в гондоле определяется как сумма значений незнакомости между всеми парами лис, которые находятся в этой гондоле. Общее значение незнакомости определяется как сумма значений незнакомости по всем гондолам.
Помогите лисе Ciel найти минимальное возможное значение общей незнакомости при некотором оптимальном распределении лис по гондолам.
Примечание
В первом примере можно распределить лис вот так: {1, 2} идут в одну гондолу, {3, 4, 5} идут в другую гондолу.
Во втором примере оптимальное распределение таково: {1, 2, 3} | {4, 5, 6} | {7, 8}.