背景 Background

为了今天的生日，飘飘乎居士可是准备很久的噢！当然，蛋糕也是少不了的。

描述 Description

为了给candy准备一个世上最美丽的蛋糕。飘飘乎居士苦心研制，最终决定制作一个k层，且体积恰好为v的蛋糕。飘飘乎居士经过多年的收集，得到了n个不同体积的蛋糕样式，但是每种只有一个。他给每个蛋糕一个美观度的评分c。现在，你要做的就是帮助飘飘乎居士选出k个组成一个美观度最大的蛋糕，注意：体积要恰好为v。

输入格式 Input Format

第一行，三个正整数 k v n

接下来n行，每行2个正整数，vi和ci，代表第i个蛋糕的体积为vi，以及美观度为ci。

输出格式 Output Format

一行，表示最大的美观度，如果不能够组成则输出"impossible"(不含双引号)。

样例输入 Sample Input

2 10 3
7 3
3 2
9 10

样例输出 Sample Output

5

注释 Hint

对于30%的数据， 0<k<=10 0<v<=100 0<n<=50

对于100%的数据 0<k<=20 0<v<=1000 0<n<=200

来源 Source

来源 飘飘乎居士——Violet Hill