Maximizing Non-expired Meal Days

JYY is a food lover who orders meals from a takeaway store. The store offers \(n\) different kinds of food, numbered from 1 to n. The i^th food has a fixed price \(p_i\) and a shelf‐life of \(s_i\) days. This means that if JYY orders food of type i on day \(t\), the food will expire after \(s_i\) days; that is, it must be consumed on or before day \(t+s_i\). In particular, if \(s_i = 0\), the food must be consumed on the same day of purchase. JYY will never eat expired food.

Every time JYY places an order, he must pay an extra delivery fee of \(f\) (regardless of the number of food items in the order). Fortunately, the delivery person is very fast and can deliver as many items as needed in an instant. JYY has \(m\) money and wishes to know the maximum number of days he can ensure having at least one meal of non-expired food per day.

How to Order?

JYY can group his orders. Assume that on a certain day \(t\) he places an order and purchases items for several days. If he uses food type \(i\) to cover a meal that is supposed to be eaten \(l\) days later (i.e. on day \(t+l\)), then the condition \(l \le s_i\) must be satisfied. For a fixed order placed on day \(t\), if he decides to cover a consecutive segment of days of length \(L\) (covering days \(t, t+1, \dots, t+L-1\)), then for each offset \(l\) (from \(0\) to \(L-1\)) he must choose a food type that satisfies \(s_i \ge l\), paying its price \(p_i\) for that day. To minimize his cost for the order, for each position \(l\) it is optimal to choose a food with the minimum possible price among those having \(s_i \ge l\).

Let us define \(A(l)\) as follows:

[ A(l) = \min_{{i \mid s_i \ge l}} p_i, \quad \text{for } l \ge 0. ]

Then, if JYY covers \(L\) days with a single order made on the same day, the total cost for that order will be:

[ \text{Cost}(L) = f + \sum_{l=0}^{L-1} A(l). ]

JYY can partition the days into several segments (each segment corresponds to one order) such that the sum of the costs of the segments does not exceed \(m\). Your task is to determine the maximum number of days that JYY can cover (i.e. enjoy a non-expired meal every day) under his budget constraint.

inputFormat

The input is given as follows:

• The first line contains three space-separated integers \(n\), \(m\), and \(f\) where \(n\) is the number of food types, \(m\) is the total money available, and \(f\) is the delivery fee per order.
• The second line contains \(n\) space-separated integers \(p_1, p_2, \dots, p_n\) representing the price of each food type.
• The third line contains \(n\) space-separated integers \(s_1, s_2, \dots, s_n\) representing the shelf-life (in days) of each food type.

Note: \(s_i\) can be 0, meaning that the food must be consumed on the day it is ordered.

outputFormat

Output a single integer representing the maximum number of days JYY can have at least one non-expired meal given his budget.

sample

2 10 2
3 4
0 1

2