Costly Contest

Time limit1sMemory limit512 MB

Summary

Split n contestants into k contiguous age divisions and pick a problem subset for each so that the fewest contestants win prizes.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Prefix sum
Solved: No attempts yet

Problem

The company Mindsight is holding a programming contest for $n$ contestants of varying ages. The contest will be separated into $k$ age divisions. The duration of the contest will be $t$ minutes, the same for all divisions. Mindsight has created a pool of $m$ available problems for use in the contest. Since all divisions compete at the same time, the same problems can be used in multiple divisions without any issues.

In each division, the participant who solves the largest number of problems gets a prize. In case of a tie (same number of problems solved), everyone tied for first place gets a prize. If no one in a division solves any problems, then everyone in that division gets a prize.

Mindsight has now come to the horrible realization that with these rules, all participants could win a prize. This could bankrupt the company! So the company has enlisted a team of experts to help resolve the situation.

The expert group analyzed the data in depth. For each of the $n$ participants, a slowness factor $s_i$ was determined. For each of the $m$ problems, a difficulty rating $d_j$ was assigned. The experts predict that the time it takes for participant $i$ to solve problem $j$ is $s_i \cdot d_j$ minutes. Participants cannot work on multiple problems in parallel, so the time it takes to solve multiple problems is the sum of the times for the individual problems. Participants always solve problems in increasing order of difficulty, starting with the easiest problem.

Now it is up to you, the underpaid intern, to configure the divisions so as to minimize the number of awarded prizes. Your task is to partition the $n$ participants into $k$ non-empty age divisions, and for each age division choose a non-empty subset of the $m$ available problems to use in that division. Each division must correspond to a contiguous age range of participants (for example, a division cannot cover ages 20 to 25 together with ages 30 to 35). The same problem may be used in multiple divisions.

Input

The first line of input contains four integers $n$ , $m$ , $k$ , $t$ ( $1 \leq n \leq 10^5$ , $1 \leq m \leq 100$ , $1 \leq k \leq n$ , $1 \leq t \leq 10^5$ ): the number of participants $n$ , the number of available problems $m$ , the number of age divisions $k$ , and the duration of the contest $t$ . The second line contains $n$ integers $s_1, \ldots, s_n$ ( $1 \leq s_i \leq 10^5$ ), the slowness factors of the participants. The participants are ordered by age, and no two participants have the same exact age. The third line contains $m$ integers $d_1, \ldots, d_m$ ( $1 \leq d_j \leq 10^5$ ), the difficulty ratings of the problems.

Output

Output a single integer, the minimum number of prize winners.

Examples2

Example 1
Input
```
4 3 2 10
2 4 3 4
11 3 6
```
Expected output
```
2
```
Example 2
Input
```
4 3 1 10
4 2 2 6
2 4 4
```
Expected output
```
2
```