3902 - 算法学习-东方博宜OJ

题目描述

小杨计划学习 $m$ 种算法，为此他找了 $n$ 道题目来帮助自己学习，每道题题目至多学习一次。

小杨对于 $m$ 种算法的初始掌握程度均为 $0$ 。第 $i$ 道题目有对应的知识点 $a_i$ ，即学习第 $i$ 道题目可以令小杨对第 $a_i$ 种算法的掌握程度提高 $b_i$ 。小杨的学习目标是对 $m$ 种算法的掌握程度均至少为 $k$ 。

小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

输入

第一行三个正整数 $m,n,k$ ，代表算法种类数，题目数和目标掌握程度。

第二行 $n$ 个正整数 $a_1 , a_2, a_3, \dots ,a_n$ ，代表每道题目的知识点。

第二行 $n$ 个正整数 $b_1 , b_2, b_3, \dots ,b_n$ ，代表每道题目提升的掌握程度。

输出

输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 -1。

样例

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

2 4 10
1 1 1 2
1 2 7 10

-1

7 12 8
1 2 3 4 4 4 5 6 6 7 7 7
10 10 10 2 5 6 10 10 7 2 8 10

说明

对于样例 $1$ ，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。

对于全部数据，保证有 $1 \le m,n \le 10^5,1 \le b_i,k \le 10^5 ,1 \le a_i \le m$ 。

子任务编号	数据点占比	$m$	$n$	$b_i$	$k$
$1$	$30\%$	$= 2$	$\le 9$	$\le 10$	$\le 10$
$2$	$30\%$	$\le 9$	$\le 9$	$\le 10$	$\le 10$
$3$	$40\%$	$\le 10^5$	$\le 10^5$	$\le 10^5$	$\le 10^5$

来源

GESP 9月认证 C++ 六级真题

标签

题目参数

上一题下一题