精衛終于快把東海填平了！只剩下了最后的一小片區域了。同時，西山上的木石也已經不多了。精衛能把東海填平嗎？
事實上，東海未填平的區域還需要至少體積為?v?的木石才可以填平，而西山上的木石還剩下?n?塊，每塊的體積和把它銜到東海需要的體力分別為?k?和?m。精衛已經填海填了這么長時間了，她也很累了，她還剩下的體力為?c。
輸入格式
輸入文件的第一行是三個整數：v,n,c。從第二行到第?n+1?行分別為每塊木石的體積和把它銜到東海需要的體力。
輸出格式
輸出文件只有一行，如果精衛能把東海填平，則輸出她把東海填平后剩下的最大的體力，否則輸出?Impossible（不帶引號）。
輸入輸出樣例
輸入?
100 2 10 50 5 50 5
輸出?
0
輸入?
10 2 1 50 5 10 2
輸出?
Impossible
說明/提示
數據范圍及約定
- 對于?20%?的數據，0<n≤50；
- 對于?50%?的數據，0<n≤1000；
- 對于?100%?的數據，0<n≤104，所有讀入的數均屬于?[0,104]，最后答案不大于?c。
//精衛填海,8/10,2個超內存
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int main(){int v, n, c;cin >> v >> n >> c;//需要的體積，石頭的數量，目前的體力值int k[100000];//體積int m[100000];//體力//或//vector<int> k(n + 1); // 體積//vector<int> m(n + 1); // 體力for (int i = 1; i <= n; i++){cin >> k[i] >> m[i];}vector<vector<int>> a(n + 1,vector<int>(v+1,0));//用i個石頭填滿j體積，需要的最少體力//必要：初始化一個很大的數表示不可能，用零塊填滿是不可能的，所有初始化最大。下面條件判斷用的是min，如果不初始化最大，那么后面一直都是for (int i = 0; i < v + 1; i++)a[0][i] = 100000;//不必要：a[i][0]是0或100000不影響結果/*for (int i = 0; i < n + 1; i++)a[i][0] = 100000;*/for (int i = 1; i <= n; i++) {for (int j = 1; j <= v; j++) {//動態規劃的核心：保持j的不變if (k[i]>=j) //一個石頭就能填滿{a[i][j] = min(a[i - 1][j], m[i]);//不放、只放一個、全放（舍）}else //一個石頭填不滿{a[i][j] = min(a[i - 1][j - k[i]]+m[i], a[i - 1][j]);//放、不放}}}if (a[n][v]>c)cout << "Impossible";elsecout << c-a[n][v];//注意用c-，不要忘記了return 0;
}
