Лиса Ciel зашла в парк аттракционов. И вот, она в очереди на колесо обозрения. В очереди стоит n людей (хотя нет, скорее лис): мы будем считать, что первая лиса стоит в начале очереди, а n-ая лиса стоит в хвосте очереди.

Всего имеется k гондол, мы распределяем лис по гондолам следующим образом:

• Когда подплывает первая гондола, q₁ лис переходят из начала очереди в подплывшую гондолу.
• Затем, когда подплывает вторая гондола, q₂ лис из начала оставшейся очереди переходит в эту гондолу.

      ...

• Оставшиеся q_k лис идут с последнюю (k-ую) гондолу.

Обратите внимание, что числа q₁, q₂, ..., q_k должны быть положительные. Из условия следует, что и q_i > 0.

Вы знаете как лисам не хочется задерживаться в гондолах с незнакомцами. Итак, Ваша задача — найти оптимальный способ размещения (то есть определить оптимальную последовательность q), чтобы угодить всем. Для каждой пары лис i и j задано значение u_ij, обозначающее степень незнакомости. Можете считать, что u_ij = u_ji для всех i, j (1 ≤ i, j ≤ n) и что u_ii = 0 для всех i (1 ≤ i ≤ n). Тогда значение незнакомости в гондоле определяется как сумма значений незнакомости между всеми парами лис, которые находятся в этой гондоле. Общее значение незнакомости определяется как сумма значений незнакомости по всем гондолам.

Помогите лисе Ciel найти минимальное возможное значение общей незнакомости при некотором оптимальном распределении лис по гондолам.