406603: GYM102452 K Key Project

A blockchain is a growing list of records, called blocks, that are linked using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data (generally represented as a Merkle tree). By design, a blockchain is resistant to modification of the data. It is called "an open, distributed ledger that can record transactions between two parties efficiently and in a verifiable and permanent way".

The Innovative Cluster Production Company (ICPC) recently decides to start a key research project related to blockchain, data mining, self-driving cars, and deep learning. There are $$$m$$$ algorithm engineers and $$$m$$$ software engineers in the ICPC. The ICPC wants to assign this new project to $$$k$$$ pairs of engineers, each of which consists of exactly one algorithm engineer and one software engineer. No engineer may be assigned to multiple pairs, otherwise the workload would be too high for the engineer.

There are $$$n$$$ buildings in the ICPC, standing sequentially one next to the other, labelled by $$$1,2,\cdots,n$$$ from left to right. The distance between the $$$i$$$-th building and the $$$(i+1)$$$-th building is $$$d_i$$$. For each engineer, we know the building where they are located, and the cost of assigning them to this project.

The two engineers in each pair need to be able to meet each other regularly to discuss the project. For each pair, the ICPC needs to pay $$$dis$$$ dollars for the cost of transportation, where $$$dis$$$ is equal to the distance between the buildings where the two engineers in the pair are located.

The ICPC is now looking for the pair assignment that minimizes the total cost of assigning engineers and transportation. Please write a program to help the ICPC find the cheapest assignment. Since key projects are the most important kind of projects for the ICPC, the details of the project must be further discussed, and the number $$$k$$$ is not yet decided. Therefore, you need to find the optimal assignment for each $$$k=1,2,\cdots,m$$$.

The input contains only a single case.

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 800$$$, $$$1\leq m\leq 50\,000$$$), denoting the number of buildings and the number of engineers. The second line contains $$$n-1$$$ integers $$$d_1,d_2,\dots,d_{n-1}$$$ ($$$1 \leq d_i \leq 10^6$$$ for $$$1 \le i \le n-1$$$), denoting the distance between each pair of adjacent buildings.

In the next $$$m$$$ lines, the $$$i$$$-th line $$$(1 \le i \le m)$$$ contains two integers $$$x_i$$$ and $$$c_i$$$ ($$$1\le x_i \le n, 1 \leq c_i\leq 10^8$$$), denoting the building where the $$$i$$$-th algorithm engineer is located and the cost of assigning this engineer to the project. In the next $$$m$$$ lines, the $$$i$$$-th line $$$(1 \le i \le m)$$$ contains two integers $$$x'_i$$$ and $$$c'_i$$$ ($$$1\le x'_i \le n, 1 \leq c'_i\leq 10^8$$$), denoting the building where the $$$i$$$-th software engineer is located and the cost of assigning this engineer to the project.

Print $$$m$$$ lines, where the $$$i$$$-th $$$(1 \le i \le m)$$$ line contains a single integer, the minimum cost if $$$k=i$$$.

4 3
1 1 1
1 1
1 2
4 6
2 1
2 2
3 5

3
8
20