题目描述

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

小杨对于$m$种算法的初始掌握程度均为0。

第$i$道题目有对应的知识点$a_i$ ，即学习第$i$道题目可以令小杨对第$a_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。

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

2 4 10
1 1 1 2
1 2 7 10

样例输出 #2

-1

提示

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

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