1440 . 誰買早餐
TopCoder
Tags
Description
還記得NPSC2005的誰先晚餐以及2007的誰來午餐嗎？
不過這題是誰買早餐。
由於培訓的時間過早，所以大多數參加的人都沒有吃早餐就來參加培訓了。
基於大家的辛勞以及儲備大家的體力，老師決定請大家吃早餐。
但因為每個人的體重不一樣，所以營養需求量也不一樣，一定要吃到營養含量不比自己的需求量低的早餐才能滿足。
老師一大早興沖沖的跑到了早餐部，卻發現每種早餐的營養含量以及價錢都不大一樣，營養越高價錢越高，而且都只剩下一份。
這下老師傷腦筋了，因為他帶的錢並不多，所以他希望花最少錢滿足大家的營養需求量。
（注意：由於公平的問題，每個人只能吃一份早餐）
Input Format
本題只有一筆測資：
第一行包含一個正整數 n ，代表參加培訓的人數（0 < n <= 1000000）
接下來有 n 行，每行有一個數字 ai，代表每人的營養需求量
第 n+2 行有一個正整數 m ，代表早餐種類的數量（0 < m <= 1000000）
接下來有 m 行，每行有兩個數字bi、ci，代表每份早餐的營養含量以及價錢
Output Format
請輸出老師最少要花多少錢，才能滿足大家的營養需求。（我們保證答案在long long int的範圍內）
若無法滿足，請輸出"Impossible."（不含雙引號）
Sample Input 1
2
5
4
3
7 7
8 8
4 4
5
4
3
7 7
8 8
4 4
Sample Output 1
11
Hints
以範例測資來說：
老師可以：
買營養價值為 7 的早餐來滿足 營養需求為 5 的同學
買營養價值為 4 的早餐來滿足 營養需求為 4 的同學
共花費 11 的金錢單位
Problem Source
原TIOJ1440 / 建中校內培訓第一次模擬考試。
Problem Setter：hallogameboy、peter50216
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |