Đồng cỏ của Farmer John được xem là một lưới ô vuông hai chiều \(N\times M\) (\(2\le N\le10^9\), \(2\le M\le2\cdot10^5\)). Ô ở hàng thứ \(x\) tính từ trên xuống và cột thứ \(y\) tính từ bên phải được ký hiệu là \((x,y)\), với \(x\in[1,N]\) và \(y\in[1,M]\). Ngoài ra, với mọi \(y\in[1,M]\), cột thứ \(y\) có chi phí \(c_y\) (\(1\le c_y\le10^9\)).

Bessie bắt đầu tại ô \((1,1)\). Nếu đang ở ô \((x,y)\), cô có thể thực hiện một trong các thao tác sau:

• Nếu \(y<M\), đi sang cột tiếp theo, tức tăng \(y\) thêm một, với chi phí \(x^2\).
• Nếu \(x<N\), đi xuống hàng tiếp theo, tức tăng \(x\) thêm một, với chi phí \(c_y\).

Cho \(Q\) truy vấn độc lập (\(1\le Q\le2\cdot10^5\)), mỗi truy vấn có dạng \((x_i,y_i)\) với \(x_i\in[1,N]\) và \(y_i\in[1,M]\). Với mỗi truy vấn, hãy tính tổng chi phí nhỏ nhất để Bessie đi từ \((1,1)\) đến \((x_i,y_i)\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\).

Dòng thứ hai chứa \(M\) số nguyên \(c_1,c_2,\ldots,c_M\), cách nhau bởi dấu cách.

Dòng thứ ba chứa \(Q\).

\(Q\) dòng cuối, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\), cách nhau bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng, lần lượt chứa đáp án cho từng truy vấn. Các giá trị có thể lớn và cần kiểu số nguyên 64 bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 1-3 thỏa mãn \(N,M\le2000\).
• Các test 4-8 thỏa mãn \(c_2>c_3>\cdots>c_M\).
• Các test 9-15 thỏa mãn \(N\le2\cdot10^5\).
• Các test 16-20 không có ràng buộc bổ sung.

Ví dụ

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

Nguồn

USACO 2021 January Contest, Platinum - Minimum Cost Paths: https://usaco.org/index.php?page=viewproblem2&cpid=1093

Tác giả: Benjamin Qi.