TopCoder

Thumb mikazuki.munechika.full.1936339
FHVirus
$\fbox{背包問題} 比 \definecolor{p}{RGB}{219,48,122}{\color{p}\fbox{FFT}} 難 QWQ$

User's AC Ratio

100.0% (40/40)

Submission's AC Ratio

36.4% (75/206)

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

2
5
4
3
7 7
8 8
4 4

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11