Cửa hàng xẻng

Một cửa hàng có $n$ chiếc xẻng, chiếc thứ $i$ có giá $a_i$ đồng. Bạn phải mua đúng $k$ chiếc xẻng, mỗi chiếc chỉ được mua nhiều nhất một lần.

Bạn có thể chia việc mua thành nhiều lượt mua. Trong một lượt mua, bạn chọn một tập con bất kỳ các xẻng chưa mua và mua cả tập con đó.

Cửa hàng có $m$ chương trình khuyến mãi. Chương trình thứ $j$ được cho bởi cặp $(x_j,y_j)$, nghĩa là: nếu trong một lượt mua bạn mua đúng $x_j$ chiếc xẻng thì $y_j$ chiếc rẻ nhất trong số đó được miễn phí.

Mỗi lượt mua được dùng nhiều nhất một chương trình khuyến mãi (cũng có thể không dùng chương trình nào). Một chương trình có thể được dùng lại ở nhiều lượt mua khác nhau, hoặc không dùng lần nào.

Hãy tính chi phí nhỏ nhất để mua đủ $k$ chiếc xẻng.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$: số xẻng trong cửa hàng, số chương trình khuyến mãi, và số xẻng phải mua.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: giá của các chiếc xẻng.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $x_j$, $y_j$ mô tả chương trình khuyến mãi thứ $j$.

Dữ liệu ra

In ra một số nguyên duy nhất: chi phí nhỏ nhất để mua đúng $k$ chiếc xẻng.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $1\le k\le min(n,2000)$
• $1\le a_i\le 2·{10}^5$
• $1\le y_j\le x_j\le n$

Ví dụ