Mindsight 公司正在举办一场面向 $n$ 名不同年龄参赛者的编程竞赛。

比赛决定分为 $k$ 个年龄组。所有组别的比赛时长均为 $t$ 分钟。Mindsight 准备了一个包含 $m$ 道题目的题库供比赛使用。由于所有组别同时进行，同一题目可以在多个组别中重复使用，不会产生任何冲突。

在每个组别中，解题数量最多的参赛者将获得奖品。如果出现平局（解题数量相同），则所有并列第一名的参赛者都将获得奖品。特别地，如果某个组别中没有人解出任何题目，则该组别中的所有参赛者都将获得奖品。

Mindsight 现在意识到一个可怕的事实：按照这些规则，所有参赛者都有可能获得奖品。这可能会导致公司破产！因此，公司聘请了一个专家团队来解决这个问题。

专家组对数据进行了深入分析。对于 $n$ 名参赛者中的每一位，都量化了他们的技能水平：对于第 $i$ 位参赛者，确定了一个“迟钝因子” $s_i$。然后，对于 $m$ 道可用题目中的每一道，都量化了其难度：对于第 $j$ 道题目，分配了一个难度等级 $d_j$。专家预测，第 $i$ 位参赛者解决第 $j$ 道题目所需的时间为 $s_i \cdot d_j$ 分钟。此外，参赛者不能同时处理多道题目，因此解决多道题目所需的时间是解决每道题目所需时间的总和。同时，参赛者总是按照难度递增的顺序解决题目，从最简单的题目开始。

现在，作为一名薪水微薄的实习生，你需要配置这些组别，以最小化获奖者的总数。你的任务是将 $n$ 名参赛者划分为 $k$ 个非空的年龄组，并为每个年龄组选择 $m$ 道可用题目中的一个非空子集。每个组别必须对应一段连续的参赛者年龄范围（例如，一个组别不能是“20-25岁或30-35岁”）。请记住，同一题目可以在多个组别中使用。

输入格式

第一行包含四个整数 $n, m, k, t$ ($1 \le n \le 10^5, 1 \le m \le 100, 1 \le k \le n, 1 \le t \le 10^5$)，分别表示参赛者人数 $n$、可用题目数量 $m$、年龄组数量 $k$ 以及比赛时长 $t$。 第二行包含 $n$ 个整数 $s_1, \dots, s_n$，表示参赛者的迟钝因子 ($1 \le s_i \le 10^5$)。参赛者已按年龄排序，且可以假设没有两名参赛者的年龄完全相同。 第三行包含 $m$ 个整数 $d_1, \dots, d_m$，表示题目的难度等级 ($1 \le d_j \le 10^5$)。

输出格式

输出一个整数，表示最少的获奖人数。

样例

样例输入 1

4 3 2 10
2 4 3 4
11 3 6

样例输出 1

2

样例输入 2

4 3 1 10
4 2 2 6
2 4 4

样例输出 2

2