Palace to Watchtowers: Bellman–Ford Verification

Cedyks, a rich and hardworking boy living in the famous palace "The Place," wants to build a wall around his palace. On this wall there are n watchtowers arranged in a line, with tower 1 and tower n at the two endpoints. The adjacent towers i and i+1 are connected by a bidirectional road of length \(w_i\).

In order to connect his palace (node 0) to the wall (nodes 1 through n), Cedyks is considering m design schemes. Under the k-th scheme, he will build \(T_k\) extra bidirectional roads between the palace and some watchtowers. Each such extra road connects the palace (node 0) and a specified watchtower \(a_i\) with length \(l_i\).

Though computing the sum of the shortest path distances from the palace to each watchtower is fairly easy, Cedyks insists on using his version of the Bellman–Ford algorithm to get a verification value for each scheme. The algorithm works as follows:

1. Number the palace as node 0 and the n watchtowers as nodes 1 through n. All roads (both the wall roads and extra roads) are bidirectional. Initialize the distance array \(d\) with \(d_0 = 0\) and \(d_i = 10^{18}\) for \(1 \le i \le n\).
2. Copy \(d\) into a helper array \(c\). Then, for every edge \((u, v, w)\) (where w is either a wall weight \(w_i\) or an extra road length \(l_i\)), update: \[ c_u = \min(c_u, d_v + w) \quad\text{and}\quad c_v = \min(c_v, d_u + w). \]
3. Let \(t\) be the number of indices where \(c\) and \(d\) differ (i.e. \(t = |\{i : c_i \neq d_i\}|\)). Add \(t\) to the verification value. If \(t = 0\) then \(d\) contains the final shortest path values and the algorithm terminates; otherwise, set \(d = c\) and repeat step 2.

For each design scheme, output two numbers separated by a space:

• The sum of the shortest distances from the palace (node 0) to each watchtower (nodes 1 through n).
• The verification value, which is defined as the sum of \(t\) over all iterations of the algorithm.

Input Format:

• The first line contains two integers \(n\) and \(m\), the number of watchtowers and the number of design schemes.
• The second line contains \(n-1\) integers \(w_1, w_2, \dots, w_{n-1}\) where \(w_i\) is the distance between watchtower \(i\) and watchtower \(i+1\).
• Then follow the descriptions of the m design schemes. For each scheme, the first line contains an integer \(T_k\) (the number of extra roads). Then \(T_k\) lines follow, each containing two integers \(a_i\) and \(l_i\), meaning there is an extra bidirectional road connecting the palace (node 0) and watchtower \(a_i\) with length \(l_i\).

Output Format:

• For each design scheme, output a single line with two space‐separated integers: the sum of the shortest distances from node 0 to nodes 1 through n and the verification value computed by the Bellman–Ford algorithm.

inputFormat

The input begins with two integers \(n\) and \(m\). The next line contains \(n-1\) integers \(w_1, w_2, \dots, w_{n-1}\). Then for each of the m design schemes:

T
a1 l1
...
aT lT

It is guaranteed that all road lengths are non-negative and that the palace is numbered 0, while watchtowers are numbered 1 to \(n\).

outputFormat

For each design scheme, output one line containing two integers: the sum of shortest distances from the palace to all watchtowers, and the verification value computed by the algorithm.

sample

3 1
2 3
1
2 1

8 3