Description

I’m sure many of you have seen Jackie Chan’s “Around the World in 80 Days,” and the intense, thrilling fight scenes must have left a deep impression. Now, there is a group of 80 people who also want to travel around the world.

They plan to split up and visit every country.

Since they are mainly located in the East, they will only move westward. Let the countries from east to west be numbered $1, \cdots, N$. If the $i$-th person’s itinerary is $P_1,P_2,\cdots ,P_k\ (0\le k\le N)$, then $P_1<P_2<\cdots <P_k$.

As we all know, China is very beautiful, so many people will pass through China during their trip. We use a positive integer $V_i$ to describe a country’s attractiveness. The larger the value of $V_i$, the more attractive the country is, and it also means that exactly $V_i$ people will pass through that country.

To save time, they plan to travel by plane. To save money, they want the total airfare to be minimal.

They are leaving tomorrow, but some people bailed at the last minute, and in the end only $M$ people will travel around the world. They want to know the minimal total cost. Please compute it.

Input Format

The first line contains two positive integers $N, M$.

The second line has $N$ positive integers, each not greater than $M$, representing $V_1,V_2,\cdots, V_N$.

Then there are $N - 1$ lines. The $i$-th of these lines contains $N - i$ integers. The $j$-th number on this line is the airfare from the $i$-th country to the $(i + j)$-th country (if this value equals $-1$, then there is no direct flight between these two countries).

Output Format

Output the minimal total cost on the first line.

6 3
2 1 3 1 2 1
2 6 8 5 0
8 2 4 1
6 1 0
4 -1
4

27

Hint

• In $10\%$ of the testdata, $M=1$.
• In $20\%$ of the testdata, $1\le M\le 2$.
• In $40\%$ of the testdata, $1\le M\le 3$.
• In $60\%$ of the testdata, $1\le M\le 4$.
• In $100\%$ of the testdata, $1 \le N\le 100$, $1\le M\le 79$.

It is guaranteed that for all input, the minimal cost is less than $10^6$.
It is guaranteed that there exists at least one feasible plan.

Jizhong League mock contest problem.
By CQF.

Translated by ChatGPT 5