Đường Đi Chi Phí Nhỏ Nhất

Cho một lưới $N\times M$ ô. Bạn xuất phát từ ô $(1,1)$ và muốn đến các ô $(x_i,y_i)$ theo yêu cầu truy vấn. Từ ô $(x,y)$, bạn có thể thực hiện hai loại di chuyển:

• Di chuyển sang phải $(x,y)\to (x,y+1)$: chi phí $x^2$
• Di chuyển xuống $(x,y)\to (x+1,y)$: chi phí $c_y$

trong đó $c_y$ là chi phí di chuyển xuống ở cột $y$, cho trước.

Với mỗi truy vấn $(x_i,y_i)$, hãy tìm chi phí nhỏ nhất để đi từ $(1,1)$ đến $(x_i,y_i)$.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $M$
• Dòng 2: $M$ số nguyên $c_1,c_2,\dots ,c_M$
• Dòng 3: số nguyên $Q$ — số lượng truy vấn
• $Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $x_i$ và $y_i$

Dữ liệu ra

In $Q$ dòng, mỗi dòng là chi phí nhỏ nhất cho truy vấn tương ứng.

Ràng buộc

• $2\le N\le {10}^9$
• $2\le M\le 2\times {10}^5$
• $1\le c_y\le {10}^9$
• $1\le Q\le 2\times {10}^5$
• $1\le x_i\le N$, $1\le y_i\le M$
• Đáp án luôn vừa trong kiểu số nguyên 64-bit

Ví dụ