Description

⼩杨计划学习 $m$ 种算法，为此他找了 $n$ 道题⽬来帮助⾃⼰学习，每道题⽬⾄多学习⼀次。

⼩杨对于 $m$ 种算法的初始掌握程度均为 $0$。第 $i$ 道题⽬有对应的知识点 $a_i$，即学习第 $i$ 道题⽬可以令⼩杨对第 $a_i$ 种算法的掌握程度提⾼ $b_i$。⼩杨的学习⽬标是对 $m$ 种算法的掌握程度均⾄少为 $k$。

⼩杨认为连续学习两道相同知识点的题⽬是不好的，⼩杨想请你编写程序帮他计算出他最少需要学习多少道题⽬才能使得他在完成学习⽬标的同时避免连续学习两道相同知识点的题⽬。

Input Format

第⼀⾏三个正整数 $m,n,k$，代表算法种类数，题⽬数和⽬标掌握程度。

第⼆⾏ $n$ 个正整数 $a_1,a_2,a_3,...,a_n$，代表每道题⽬的知识点。

第⼆⾏ $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

Hint

样例解释

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

数据范围

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

Source

GESP六级202409