算法学习

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

输入格式

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

输出格式

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

样例

样例输入1：

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

一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。

样例输出1：

4

样例输入2：

2 4 10
1 1 1 2
1 2 7 10

样例输出2：

-1

数据范围

对于全部数据，保证有 1 ≤ m ≤ 10^5，1 ≤ n ≤ 10^5，1 ≤ k ≤ 10^5，1 ≤ a_i ≤ m，1 ≤ b_i ≤ 10^4。