G - Automat Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

AtCoder 王国では、1 ドル紙幣と K ドル紙幣の 2 種類の紙幣が流通しています。

AtCoder 王国にある J 社の全自動食堂では、デザートやドリンクが商品として売られています。

J 社の全自動食堂には、N 個のデザートを売るデザート販売機と、M 個のドリンクを売るドリンク販売機があります。 デザートには 1 から N までの、ドリンクには 1 から M までの番号が付けられています。

デザート i の価格は A_i ドル、ドリンク j の価格は B_j ドルです。

支払いに使う紙幣として、デザート販売機は 1 ドル紙幣と K ドル紙幣の両方を受け入れますが、ドリンク販売機は K ドル紙幣しか受け入れません。 どちらの販売機も、お釣りはすべて 1 ドル紙幣のみを使って返します。 同じ商品を 2 個以上買うことはできません。

高橋君は 1 ドル紙幣 X 枚と K ドル紙幣 Y 枚を持って J 社の全自動食堂にやってきました。

高橋君が手持ちの紙幣で買える商品の組合せにおいて、購入できる商品数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq K \leq 10^9
  • 0 \leq X \leq 10^{15}
  • 0 \leq Y \leq 10^9
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
X Y
A_1 \dots A_N
B_1 \dots B_M

出力

答えを出力せよ。

入力例 1

2 3 10
50 6
22 30
20 12 24

出力例 1

4

以下の手順で買い物を行うことで、4 個の商品を買うことができます。

  • 10 ドル紙幣 2 枚を払ってドリンク 1 を買う。お釣りは無し。
  • 10 ドル紙幣 2 枚を払ってドリンク 2 を買う。お釣りは 1 ドル紙幣 8 枚。
  • 10 ドル紙幣 2 枚と 1 ドル紙幣 10 枚を払ってデザート 2 を買う。お釣りは無し。
  • 1 ドル紙幣 22 枚を払ってデザート 1 を買う。お釣りは無し。

4 個よりも多く買うことはできないので、4 が答えとなります。

入力例 2

1 7 67
677677677766666 0
777666777
20 12 24 67 67 67 67

出力例 2

1

以下の手順で買い物を行うことで、1 個の商品を買うことができます。

  • 1 ドル紙幣 600000777666777 枚を払ってデザート 1 を買う。お釣りは 1 ドル紙幣 600000000000000 枚。

1 個よりも多く買うことはできないので、1 が答えとなります。

入力例 3

20 20 30
605776135 133105105
97363214 218434035 697895427 109255624 299037330 227873982 195540071 411713803 828357845 244535208 138059186 639510883 39844882 707397687 371274487 696536603 351588202 319490007 47121612 87169661
32256972 567982330 554885983 299718223 443859449 687952877 264684780 666659381 576335424 941894234 406248934 321334900 423472560 863738035 213143887 384834384 468161291 673106162 164648316 15903323

出力例 3

22

Score : 425 points

Problem Statement

In the Kingdom of AtCoder, two kinds of bills are in circulation: 1-dollar bills and K-dollar bills.

At Company J's fully automated cafeteria in the kingdom, desserts and drinks are sold as products.

The company's fully automated cafeteria has a dessert vending machine that sells N desserts, and a drink vending machine that sells M drinks. The desserts are numbered 1 through N, and the drinks are numbered 1 through M.

Dessert i costs A_i dollars, and drink j costs B_j dollars.

As payment, the dessert vending machine accepts both 1-dollar bills and K-dollar bills, but the drink vending machine accepts only K-dollar bills. Both vending machines give change using only 1-dollar bills. You cannot buy two or more of the same product.

Takahashi came to Company J's fully automated cafeteria with X 1-dollar bills and Y K-dollar bills.

Among the combinations of products that he can buy with the bills he has, find the maximum number of products he can purchase.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq K \leq 10^9
  • 0 \leq X \leq 10^{15}
  • 0 \leq Y \leq 10^9
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
X Y
A_1 \dots A_N
B_1 \dots B_M

Output

Output the answer.

Sample Input 1

2 3 10
50 6
22 30
20 12 24

Sample Output 1

4

By shopping as follows, Takahashi can buy four products.

  • Pay two 10-dollar bills to buy drink 1. No change.
  • Pay two 10-dollar bills to buy drink 2. The change is eight 1-dollar bills.
  • Pay two 10-dollar bills and ten 1-dollar bills to buy dessert 2. No change.
  • Pay twenty-two 1-dollar bills to buy dessert 1. No change.

He cannot buy more than four products, so the answer is 4.

Sample Input 2

1 7 67
677677677766666 0
777666777
20 12 24 67 67 67 67

Sample Output 2

1

By shopping as follows, Takahashi can buy one product.

  • Pay 600000777666777 1-dollar bills to buy dessert 1. The change is 600000000000000 1-dollar bills.

He cannot buy more than one product, so the answer is 1.

Sample Input 3

20 20 30
605776135 133105105
97363214 218434035 697895427 109255624 299037330 227873982 195540071 411713803 828357845 244535208 138059186 639510883 39844882 707397687 371274487 696536603 351588202 319490007 47121612 87169661
32256972 567982330 554885983 299718223 443859449 687952877 264684780 666659381 576335424 941894234 406248934 321334900 423472560 863738035 213143887 384834384 468161291 673106162 164648316 15903323

Sample Output 3

22