Description

Albert_Li 所在的学校又没有拿到南京站现场赛名额，于是他开始研究组委会的名额分配规则。

本次网络预选赛共有 $m$ 支队伍，分别来自 $n$ 所学校。所有队伍按照成绩从高到低排列，第 $j$ 名队伍来自学校 $p_j$。

每所学校 $i$ 已经通过承办比赛、进入世界总决赛等方式获得了 $c_i$ 个固定名额。

除此之外，组委会准备制定两个排名门槛 $x$ 和 $y$，满足 $0\le x,y\le m$。

其中：

• 如果学校 $i$ 至少有一支队伍位于前 $x$ 名，那么该学校额外获得 $1$ 个名额；
• 如果学校 $i$ 至少有三支队伍位于前 $y$ 名，那么该学校额外获得 $1$ 个名额。

$x$ 和 $y$ 都可以是 $0$。前 $0$ 名中没有任何队伍，不要求 $x\le y$。

设学校 $i$ 一共有 $t_i$ 支参赛队伍。由于同一所学校最多可以派出 $4$ 支队伍，并且不能派出不存在的队伍，因此它最终获得的名额数为:

其中：

• $f_i$ 表示学校 $i$ 排名最高的队伍的名次；若学校没有队伍，则 $f_i=+\infty$；
• $g_i$ 表示学校 $i$ 排名第三高的队伍的名次；若学校不足三支队伍，则 $g_i=+\infty$；
• $[P]$ 在命题 $P$ 成立时等于 $1$，否则等于 $0$。

赛场最多只能容纳 $k$ 支队伍，因此必须满足 $\sum_{i=1}^{n}q_i\le k$。

组委会希望两个门槛尽可能宽松，因此需要最大化 $x+y$ 且如果存在多组最优答案，则最大化 $x$。

请你求出组委会最终应当选择的 $x$ 和 $y$。

Format

Input

第一行包含三个整数 $n,m,k(1\le n,m\le 2\cdot 10^5)$，分别表示学校数量、队伍数量和赛场容量。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n(0\le c_i\le \min(4,t_i)$，表示每所学校的固定名额数。

第三行包含 $m$ 个整数 $p_1,p_2,\ldots,p_m(1\le p_j\le n,)$，其中 $p_j$ 表示排名第 $j$ 的队伍所属的学校。

题目保证 $\sum_{i=1}^{n}c_i\le k\le \sum_{i=1}^{n}\min(4,t_i)$。

Output

输出两个整数 $x$ 和 $y$，表示满足条件的最优排名门槛。

Samples

4 10 7
1 2 0 1
1 2 1 3 2 1 4 3 3 2

10 5

Note

选择 $x=10,\ y=5$ 时：

• 学校 $1$ 有队伍进入前 $10$ 名，但前 $5$ 名中只有两支队伍，获得 $2$ 个名额；
• 学校 $2$ 有队伍进入前 $10$ 名，获得 $3$ 个名额；
• 学校 $3$ 获得 $1$ 个名额；
• 学校 $4$ 只有一支队伍，因此最多获得 $1$ 个名额。

总名额数为 $2+3+1+1=7$。可以证明，不存在满足容量限制且 $x+y>15$ 的方案。