#2338. GESP-202409-算法学习002

GESP-202409-算法学习002

问题背景

小杨制定了一个教学表,为优先级为了m道题目提前自己学习,每道题目至少学习一次。

小杨的每道题的掌握难度均为0,题目拥有的初始知识点数。刷学习题目可以小杨增加对知识点的掌握程度。小杨每学到相关的掌握的数量就是题目知识点的和。


问题描述

小杨从m道题目中预期刷到n道题目的最优难度,小杨请你编写程序计算刷m道题目能掌握多少道题目才能在最短的连续学习时间内连续掌握知识点和。


格式

输入

第一行三个正整数m, n, k,代表选择m次,题目目标n和k题。

第二行m个正整数a1, a2, ..., am,代表题目知识点数。

第三行n个正整数b1, b2, ..., bn,代表被选题目拥有的初始掌握难度。


输出

输出一个整数,代表小杨最少学习到的题目数量,如果不存在直接输出-1。


样例

输入数据 1

3 3 6 1 2 3 1 2 3

输出数据 1

1

输入数据 2

2 2 10 1 2 1 7

输出数据 2

-1

提示

对于样例1,小杨优先学习第3题一次,第二道题目,第三道题目,第三道题目。

子任务编号 数据量占比 m n k
1 30% m, n ≤ 5, k ≤ 10
2 m, n ≤ 10, k ≤ 10
3 40% m, n ≤ 100, k ≤ 100

对于全部数据,保证: 1 ≤ m, n ≤ 10^5,k ≤ 10^5,1 ≤ ai, bi ≤ 10^5