4332: [GESP202409六级] 算法学习
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## 题目背景
2024 年 9 月 GESP C++ 六级编程第 2 题
## 题目描述
小杨计划学习 $m$ 种算法，为此他找了 $n$ 道题目来帮助自己学习，每道题目最多学习一次。
小杨对于 $m$ 种算法的初始掌握程度均为 $0$。第 $i$ 道题目有对应的知识点 $a_i$，即学习第 $i$ 道题目可以令小杨对第 $a_i$ 种算法的掌握程度提高 $b_i$。小杨的学习目标是对 $m$ 种算法的掌握程度均至少为 $k$。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。
输入
## 输入格式
第一行三个正整数 $m,n,k$，代表算法种类数，题目数和目标掌握程度。
第二行 $n$ 个正整数 $a_1,a_2,a_3,...,a_n$，代表每道题目的知识点。
第三行 $n$ 个正整数 $b_1,b_2,b_3,...,b_n$，代表每道题目提升的掌握程度。
输出
## 输出格式
输出一个整数，代表⼩杨最少需要学习题目的数量，如果不存在满足条件的⽅案，输出 $-1$。
样例输入 复制
3 5 10
1 1 2 3 3
9 1 10 10 1样例输出 复制
4提示
## 样例1
```input1
3 5 10
1 1 2 3 3
9 1 10 10 1
```
```output1
4
```
## 样例2
```input2
2 4 10
1 1 1 2
1 2 7 10
```
```output2
-1
```
## 样例解释
对于样例1，⼀种最优学习顺序为第⼀道题，第三道题，第四道题，第⼆道题。
## 数据范围
| 子任务编号 | 数据点占比 | $m $ | $n $ | $b_i $ | $k $ |
| ---------- | ---------- | ----------- | ----------- | ----------- | ----------- |
| 1 | $30\%$ | $= 2$ | $\leq 9$ | $\leq 10$ | $\leq 10$ |
| 2 | $30 \%$ | $\leq 9$ | $\leq 9$ | $\leq 10$ | $\leq 10$ |
| 3 | $40\%$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ |
对于全部数据，保证有 $1 \leq m,n \leq 10^5,1 \leq b_i,k \leq 10^5,1 \leq a_i \leq m$。