Description

小杨计划学习m种算法，为此他找了n道题目来帮助自己学习，每道题目至多学习一次。 小杨对于m种算法的初始掌握程度均为0。第i道题目有对应的知识点$a_i$，即学习第 道题目可以令小杨对第$a_i$种算法的掌握程度提高 。小杨的学习目标是对m种算法的掌握程度均至少为k。 小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

Input Format

第一行三个正整数$m,n,k$，代表算法种类数，题目数和目标掌握程度。 第二行 个正整数$a_1,a_2,a_3,……,a_n,$，代表每道题目的知识点。 第二行 个正整数$b_1,b_2,b_3,……,b_n,$，代表每道题目提升的掌握程度。

Output Format

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

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

4

2 4 10
1 1 1 2
1 2 7 10

-1