题目描述

小杨计划学习 $m$ 种算法，共有 $n$ 道题可供选择。第 $i$ 道题对应知识点 $a_i$，学习后可使第 $a_i$ 种算法的掌握程度增加 $b_i$。初始时每种算法的掌握程度均为 $0$。小杨希望每种算法的掌握程度都至少为 $k$，并且不连续学习两道相同知识点的题。请计算最少需要学习多少道题；若无法做到，输出 $-1$。

输入格式

第一行输入三个正整数 $m,n,k$。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每道题的知识点。

第三行输入 $n$ 个正整数 $b_1,b_2,\ldots,b_n$，表示每道题带来的掌握程度提升。

输出格式

输出一个整数，表示最少需要学习的题目数量；若不存在满足条件的学习方案，输出 $-1$。

3 5 10
1 1 2 3 3
9 1 10 10 1

4

数据范围与提示

• $1 \le m,n \le 10^5$
• $1 \le a_i \le m$
• $1 \le b_i,k \le 10^5$
• 学习顺序可自行安排，但相邻两道题的知识点不能相同。
• 样例可学习第 $1,3,4,5$ 道题。

来源

GESP 2024年9月 C++ 六级