TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

100.0% (23/23)

Submission's AC Ratio

30.6% (33/108)

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

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 15000 65536 65536
1 15000 65536 65536
2 15000 65536 65536
3 15000 65536 65536
4 15000 65536 65536
5 15000 65536 65536
6 15000 65536 65536
7 15000 65536 65536
8 15000 65536 65536
9 15000 65536 65536
10 15000 65536 65536