비용이 드는 대회

시간 제한1초메모리 제한512 MB

요약

참가자 n명을 나이순으로 k개의 연속 구간으로 나누고, 각 구간에 문제 부분집합을 골라 상을 받는 참가자 수가 최소가 되게 하는 문제입니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

Mindsight 회사는 나이가 서로 다른 $n$ 명의 참가자를 대상으로 프로그래밍 대회를 연다. 대회는 $k$ 개의 연령 부문으로 나뉜다. 대회 시간은 모든 부문이 같은 $t$ 분이다. Mindsight는 대회에 쓸 문제 $m$ 개를 미리 준비했다. 모든 부문이 동시에 경쟁하므로 같은 문제를 여러 부문에서 사용해도 문제가 없다.

각 부문에서 문제를 가장 많이 푼 참가자가 상을 받는다. 동점이면 공동 1등인 모든 참가자가 상을 받는다. 특히 부문 안의 아무도 문제를 풀지 못하면 그 부문의 모든 참가자가 상을 받는다.

Mindsight는 이 규칙대로라면 모든 참가자가 상을 받을 수도 있다는 끔찍한 사실을 깨달았다. 이러면 회사가 파산할 수도 있다! 그래서 회사는 상황을 해결하려고 전문가 팀을 꾸렸다.

전문가 팀은 데이터를 깊이 분석했다. $n$ 명의 참가자 각각에 대해 느림 계수 $s_i$ 가 정해졌다. $m$ 개의 문제 각각에는 난이도 $d_j$ 가 매겨졌다. 전문가들은 참가자 $i$ 가 문제 $j$ 를 푸는 데 $s_i \cdot d_j$ 분이 걸린다고 예측한다. 참가자는 문제를 동시에 여러 개 풀 수 없으므로, 여러 문제를 푸는 데 걸리는 시간은 각 문제를 푸는 시간의 합이다. 참가자는 항상 가장 쉬운 문제부터 난이도가 높아지는 순서로 푼다.

이제 저임금 인턴인 당신이 상을 받는 사람 수를 최소로 만들도록 부문을 구성할 차례다. 참가자 $n$ 명을 공집합이 아닌 $k$ 개의 연령 부문으로 나누고, 각 부문마다 $m$ 개의 문제 중 공집합이 아닌 부분집합을 골라 사용하면 된다. 각 부문은 참가자의 연속된 나이 범위에 해당해야 한다(예를 들어 한 부문이 20세에서 25세와 30세에서 35세를 함께 묶을 수는 없다). 같은 문제를 여러 부문에서 사용해도 된다.

입력

입력의 첫 줄에는 네 정수 $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$ ). 각각 참가자 수 $n$ , 문제 수 $m$ , 부문 수 $k$ , 대회 시간 $t$ 이다. 둘째 줄에는 참가자의 느림 계수 $s_1, \ldots, s_n$ 이 주어진다 ( $1 \leq s_i \leq 10^5$ ). 참가자는 나이순으로 정렬되어 있으며, 나이가 완전히 같은 참가자는 없다. 셋째 줄에는 문제의 난이도 $d_1, \ldots, d_m$ 이 주어진다 ( $1 \leq d_j \leq 10^5$ ).

출력

상을 받는 사람 수의 최솟값을 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
4 3 2 10
2 4 3 4
11 3 6
```
예상 출력
```
2
```
예제 2
입력
```
4 3 1 10
4 2 2 6
2 4 4
```
예상 출력
```
2
```