Description
小杨计划学习m种算法，为此他找了n道题来帮助学习，每道题最多学习次一次。
小杨对于m种算法的初始掌握程度均为0。第i道题有对应的知识点ai，即学习第i道题可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习标是对m种算法的掌握程度均至少为k 。
小杨认为连续学习两道相同知识点的题是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题。
Input
第一行三个正整数m, n, k，代表算法种类数，题目数和目标掌握程度。
第二行n个正整数a1, a2, a3, ..., an ，代表每道题的知识点。
第三个n正整数b1, b2, b3, ... bn，代表每道题提升的掌握程度。
Output
输出一个整数，代表小杨最少需要学习题的数量，如果不存在满足条件的方案，输出 -1。
3 5 10
1 1 2 3 3
9 1 10 10 1
HINT
样例输入2
2 4 10
1 1 1 2
1 2 7 10
样例输出 2
-1
|
子任务编号
|
数据点占比
|
m
|
n
|
bi
|
k
|
|
1
|
30%
|
=2
|
<=9
|
<=10
|
<=10
|
|
2
|
30%
|
<=9
|
<=9
|
<=10
|
<=10
|
|
3
|
40%
|
<=100000
|
<=100000
|
<=100000
|
<=100000
|
对于全部数据，保证有1<=m,n<=10
5, 1<=b
i, k<=10
5; 1<= a
i <=m