Đàm phán

Alice có $n$ mảnh đất được đánh số từ $1$ tới $n$, mảnh đất thứ $i$ có giá trị $a_i$.

Alice chuẩn bị cho $q$ cuộc đàm phán độc lập với nhau. Trong mỗi cuộc đàm phán, mỗi mảnh đất được gán một hệ số, ban đầu tất cả hệ số đều bằng $0$. Cuộc đàm phán gồm $t$ lợi ích; mỗi lợi ích cho bởi hai số nguyên $x$ và $y$, có nghĩa là: mọi vị trí $j$ mà $j$ chia hết cho $x$ sẽ được cộng thêm $y$ vào hệ số của nó.

Sau khi áp dụng hết $t$ lợi ích, Alice được sắp xếp lại $n$ giá trị $a_1,a_2,\dots ,a_n$ lên $n$ vị trí một cách tùy ý (mỗi giá trị dùng đúng một lần). Giá trị của cuộc đàm phán là tổng của hệ số nhân với giá trị đặt tại vị trí đó, lấy trên tất cả các vị trí.

Với mỗi cuộc đàm phán, hãy tìm giá trị lớn nhất mà Alice có thể đạt được. Các hệ số được đặt lại về $0$ ở đầu mỗi cuộc đàm phán.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Tiếp theo là $q$ khối mô tả các cuộc đàm phán. Mỗi khối bắt đầu bằng một dòng chứa số nguyên $t$, sau đó là $t$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là giá trị lớn nhất của cuộc đàm phán thứ $i$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le q\le {10}^4$
• $1\le a_i\le {10}^9$
• $1\le t\le 10$
• $1\le x\le 100$, $1\le y\le 100$

Ví dụ