#P2380. 点兵点将

点兵点将

众所不知,LLM是一个红警3的高手,由于要出题所以好几天没有玩结果连简单的电脑都打不过了,因此LLM就可耻的开了外挂虐电脑,外挂的效果是这样的:

当LLM消灭一个属性为ai的单位时,他就能免费制造一个属性为bi的单位,如果他犹豫了一下(甚至可能手速慢了一点)就会错失良机,不能再免费制造它

为了简化这个问题,我们假设如果一个A属性和一个B属性的去同时打一个C属性的单位(A+B <=C)那么A和B会死亡,而C的属性会剩下C-A-B

现在假设LLM初始有一个属性为n的单位,由于其上司的吃喝嫖赌,欠了3.5个亿带着小姨子跑了(不懂什么梗请百度《浙江温州江南皮革场倒闭了》)所以LLM没有任何金钱,现在它要按顺序消灭m个敌人,为了磨练自己的技术,LLM希望自己制造的总单位数越少越好,请问LLM制造的单位数量最少是多少?

Input

每个测试文件包含不多于10组测试样例

每个测试样例第一行为nm

接下来两行各m个数字第二行为ai,第三行为bi

1<=m<=25555

1<=ai,bi,n<=1000

Output

输出仅包含一行,为一个整数,代表最少需要制造的单位数量

如果LLM开外挂都无法打败敌人,输出-1

Sample Input

2 2
1 1
10 10
2 3
1 10 1
1 10 10

Sample Output

0
-1

HINT

Source