题面描述

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

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

小杨认为连续学习两道相同知识点的题目是不好的，请你编写程序帮他计算出他最少需要学习多少道题目才能同时满足上述两个条件；如果不存在满足条件的方案，输出-1。

输入格式

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

第二行n个正整数a₁，a₂，...，aₙ，代表每道题目的知识点。

第三行n个正整数b₁，b₂，...，bₙ，代表每道题目提升的掌握程度。

样例

样例1

输入：

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

输出：

4

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

样例2

输入：

2 4 10
1 1 1 2
1 2 7 10

输出：

-1

数据范围

对于全部数据，保证有 1 ≤ m,n ≤ 10⁵, 1 ≤ bᵢ,k ≤ 10⁵, 1 ≤ aᵢ ≤ m。