import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 1번째 줄: N, M, K
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long K = Long.parseLong(st.nextToken());
// 2번째 줄: X, Y
st = new StringTokenizer(br.readLine());
long X = Long.parseLong(st.nextToken()); // 1달러 지폐 수 (최대 10^15)
long Y = Long.parseLong(st.nextToken()); // K달러 지폐 수 (최대 10^9)
// 3번째 줄: A1 ... AN (디저트 가격)
long[] A = new long[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
// 4번째 줄: B1 ... BM (음료 가격) K달러만 받음
long[] B = new long[M];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
B[j] = Long.parseLong(st.nextToken());
}
long total_amount = X + K*Y;
Arrays.sort(A);
Arrays.sort(B);
// remains 의 index는 음료 구매 수, value는 그 구매 후의 1달러 수
long[] remains = new long[M+1];
remains[0] = total_amount;
for (int j = 1; j <= M; j++) {
if(Y*K-B[j-1] >= 0) {
// f1
long paid_k = (B[j-1]+K-1)/K;
long rest = paid_k*K - B[j-1];
Y -= paid_k;
// f2
remains[j] = remains[j-1] -paid_k*K+ rest;
// System.out.println(paid_k + " " + rest);
} else {
remains[j] = -1;
break;
}
}
// remains 의 각 금액에 따라 구매할 수 있는 디즈트의 최대개수를 구하기
// M개수가 10^5수준, N을 그대로 순회하면 시간초과니 10^4 이하로 하기를 권장.
// 이를 만족하는 방법은 logN의 이진탐색뿐.
//remains 배열 따로 안만들고 위의 for문에서 바로 이진탐색 했으면 메모리절약 됐을 듯.
long[] acc_A = new long[N+1];
for (int i=1; i<=N; i++) {
acc_A[i] = acc_A[i-1] + A[i-1];
}
long max_v = 0;
// f3 f4
for (int j=0; j<=M; j++) {
// System.out.println(remains[j]);
if(remains[j] == -1) break;
long buy_count = j;
int l = 0; // 뭐...디저트도 하나도 안살 수 있으니 l은 0으로 해야하나
int r = N;
int max_desert = 0;
while (l<=r) {
int m = (l+r)/2;
// f5
// m개 사기에는 돈이 부족하다 -> m을 줄여야지.
if(acc_A[m] > remains[j]) r = m -1;
else {
max_desert = m;
l = m+1;
}
}
// System.out.println(max_v + " j" + j + " max_desert" +max_desert);
max_v = Math.max(max_v, max_desert+j);
}
System.out.println(max_v);
//feedback
//
}
}
To embed this project on your website, copy the following code and paste it into your website's HTML: