Zeyna is an amazing resource manager for the International Space Station. Zeyna helps the government send resources to the International Space Station. She is tasked with delivering \(\mathbf{N}\) batches of resources for \(\mathbf{N}\) months. However, each of the shipments costs a fixed transportation cost \(\mathbf{K}\). So, to save on shipping costs, Zeyna can also choose to bunch the needed resources for the next months and send them earlier than needed.

However, resources decay in time. Therefore, if Zeyna decides to send a batch for multiple months, additional resources should be added to meet the needed demand. Thankfully, data scientists have computed how much these additional resources will cost. If the batches for month i to month j (inclusive) are sent on month i, additional resources of cost \(a_{ij}\) will have to be added. Of course, there is no additional cost if only the batch for month i is sent on month i by itself, as there is no need for any additional resource in the first place.

Zeyna wants your help to optimize the total cost of transportation and resources for \(\mathbf{N}\) months.

\(\mathbf{a_{ii}}\) is 0 for every \(\mathbf{i}\) since there is no additional resource cost for delivering resources for a single month. So, there would only be a transportation cost for those kinds of shipments.

For any given month \(\mathbf{i}\), sending resources for more number of months will always be costlier than sending for less number of months (\(\mathbf{a_{ij}<a_{i(j+x)}}\) for any positive \(\mathbf{x}\) value)

Input

The first line of input contains 2 integers \(\mathbf{N}\) and \(\mathbf{K}\). The number of months and the fixed transportation cost.

• \(1 \leq \mathbf{N} \leq 1000\)
• \(1 \leq \mathbf{K} \leq 300000\)

Next \(\mathbf{N-1}\) lines contain the additional resource costs \(\mathbf{a_{ij}}\). \(\mathbf{a_{ij}}\) is the additional resource cost of delivering resources from \(\mathbf{i^{th}}\) month up to \(\mathbf{j^{th}}\) month, inclusive. For each line, \(\mathbf{j}\) is from \(\mathbf{i + 1}\) to \(\mathbf{N}\). Each line contains \(\mathbf{N - i - 1}\) numbers.

• \(1 \leq \mathbf{a_{ij}} \leq 10^{12}\)

Output

The output contains 1 integer.

• Print the minimum total cost of delivering resources for \(\mathbf{N}\) months.

Example

Input:

5 5
3 5 14 20
1 7 10
3 5
2

Output:

17

Explanation

Input 1

• The first line 3 5 14 20 represents additional resource cost of delivering resources from \(1^{st}\) month up to \(2^{nd},3^{rd},4^{th},5^{th}\) months.
• The second line 1 7 10 represents additional resource cost of delivering resources from \(2^{nd}\) month up to \(3^{rd},4^{th},5^{th}\) months.
• The third line 3 5 represents additional resource cost of delivering resources from \(3^{rd}\) month up to \(4^{th},5^{th}\) months.
• The fourth line 2represents additional resource cost of delivering resources from \(4^{th}\) month up to \(5^{th}\) months.

We can get the minimum cost in 2 shipments.

• Shipment for months 1-3 costs \(5 + 5 = 10\) (additional resource cost of 1-3 + fixed loading cost)
• Shipment for months 4-5 costs \(2 + 5 = 7\)(additional resource cost of 4-5 + fixed loading cost)

which is the lowest cost of loading: 17