Problem Statement

Takahashi runs a stall at a summer festival. The stall sells N types of products, and he has hired M part-time workers.

Takahashi has S yen as his starting capital. He wants to operate the stall for as many days as possible while paying the daily wages to the part-time workers within this budget.

Each part-time worker has a fixed daily wage. The daily wage of the j-th part-time worker is B_j yen. To operate the stall for one day, he must pay the daily wages to all part-time workers.

On the other hand, the stall's revenue is determined by the popularity of each product. The i-th product has a "popularity" value A_i, and the daily revenue is the sum of the popularity values of all products, i.e., \sum_{i=1}^{N} A_i yen.

During one day of operation, the revenue is earned first, and then the daily wages are paid to all part-time workers. In other words, the change in the amount of money held at the end of a day's operation is +\left(\sum_{i=1}^{N} A_i\right) - \left(\sum_{j=1}^{M} B_j\right) yen.

Takahashi's money after paying the daily wages on each business day must not become less than 0 yen (exactly 0 yen is acceptable).

Determine the maximum number of days Takahashi can operate the stall. If he can continue operating indefinitely, output -1.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq S \leq 10^{18}
• 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 inputs are integers.

Sample Input 1

2 2 10
3 2
4 4

Sample Output 1

3

Sample Input 2

3 2 5
10 5 5
8 7

Sample Output 2

-1

Sample Input 3

3 4 1000000000000000000
100000000 200000000 300000000
300000000 200000000 150000000 100000000

Sample Output 3

6666666666

Problem Statement

Takahashi is participating in a cooking contest. In the contest, he will prepare a dish using N ingredients.

The ingredients are numbered from 1 to N, and the deliciousness of the i-th ingredient is A_i. Takahashi has prepared one substitute ingredient for each ingredient. If he replaces the i-th ingredient with its substitute, its deliciousness changes to B_i.

According to the contest rules, Takahashi must choose exactly K out of the N ingredients and replace them with their substitute ingredients. The deliciousness of ingredients that are not replaced remains A_i.

The overall deliciousness of the dish is determined by the sum of the deliciousness values of all N ingredients after replacement. Find the maximum possible overall deliciousness of the dish when the K ingredients to replace are chosen optimally.

Constraints

• 1 \leq K \leq N \leq 3 \times 10^5
• -10^9 \leq A_i \leq 10^9
• -10^9 \leq B_i \leq 10^9
• All input values are integers

Sample Input 1

4 2
5 2 4 1
3 10 1 7

Sample Output 1

26

Sample Input 2

3 2
8 -1 5
4 -3 2

Sample Output 2

7

Sample Input 3

8 4
3 -5 12 7 0 9 -2 4
8 -10 6 20 -1 9 5 -3

Sample Output 3

53

Sample Input 4

20 9
4 -7 13 0 25 -12 8 19 -3 6 11 -1 14 -9 2 17 5 -6 10 1
9 -20 5 7 30 -4 -8 18 12 6 -2 3 16 -15 20 10 -1 14 0 1

Sample Output 4

181

Sample Input 5

1 1
-1000000000
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is a mountain photographer. There are N mountain peaks lined up in a straight line from west to east, and the elevation of the i-th peak from the west is H_i.

Takahashi wants to take a photo of the peaks contained in an interval [l, r] (1 \leq l \leq r \leq N). Here, the interval [l, r] refers to the contiguous sequence of peaks consisting of the l-th, (l+1)-th, \ldots, r-th peaks from the west.

To take a beautiful photo, the sequence of peaks must be mountain-shaped.

An interval [l, r] of peaks is mountain-shaped if there exists an integer k (l \leq k \leq r) such that:

H_l < H_{l+1} < \cdots < H_k > H_{k+1} > \cdots > H_r

That is, the elevation strictly increases from l to k, and strictly decreases from k to r. In particular, if l = r (only one peak), it is also mountain-shaped. If k = l, the entire sequence is strictly decreasing, and if k = r, the entire sequence is strictly increasing; these cases are also considered mountain-shaped.

(Note: Because the definition of mountain-shaped uses strict inequalities, an interval containing adjacent peaks of equal elevation (H_i = H_{i+1}) cannot be mountain-shaped.)

Furthermore, Takahashi wants to take a dynamic photo, so he only considers an interval as a shooting candidate if it is mountain-shaped and the difference between the maximum and minimum elevations in the interval, i.e.,

\max(H_l, H_{l+1}, \ldots, H_r) - \min(H_l, H_{l+1}, \ldots, H_r)

is at least K.

If there are any shooting candidate intervals, find the maximum number of peaks r - l + 1 contained in such an interval. If no shooting candidates exist, output 0.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq K \leq 10^9
• 1 \leq H_i \leq 10^9
• H_i are not necessarily distinct.
• All input values are integers.

Sample Input 1

7 4
1 3 5 4 2 6 1

Sample Output 1

5

Sample Input 2

5 10
1 2 3 4 5

Sample Output 2

0

Sample Input 3

15 20
10 15 30 25 20 20 21 22 19 18 40 35 30 28 50

Sample Output 3

5

Sample Input 4

50 100
500 480 460 470 520 610 700 650 600 550 550 560 570 580 590 300 310 320 330 340 330 320 310 305 1000 900 800 700 600 500 400 410 420 430 440 450 460 470 480 490 490 100 200 300 400 350 250 150 50 25

Sample Output 4

9

Sample Input 5

1 1000000000
1000000000

Sample Output 5

0

Problem Statement

Takahashi works as an administrator at a university printing center. In this printing center, there are N printers, numbered 1 to N.

Each printer i has a maximum page capacity W_i that it can process in a single print job, and a processing time T_i required to process one job. Regardless of the number of pages in a job, the time required for printer i to process a single job is always T_i.

Today, M print jobs have arrived at the printing center. Each job j has a specified number of pages P_j to be printed.

A single job cannot be split and must be processed by a single printer whose maximum page capacity is at least the number of pages in the job. That is, to process job j with printer i, we must have W_i \geq P_j.

Each printer can process at most one job at a time. As soon as a printer finishes processing a job, it can immediately start processing the next one. All printers are available starting from time 0. Each job can start processing at any time, but all jobs must be processed.

Takahashi wants to minimize the earliest time by which all jobs are processed, i.e., the completion time of the last job.

If it is possible to process all M jobs, output the earliest time by which all jobs can be completed. If there is any job that cannot be processed (i.e., there is a job with a number of pages that no printer can handle), output -1.

Constraints

• 1 \leq N, M
• N + M \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

2 3
10 5
20 7
8
15
10

Sample Output 1

10

Sample Input 2

2 3
5 3
10 2
4
11
8

Sample Output 2

-1

Sample Input 3

5 10
30 8
10 3
50 15
20 6
40 10
5
12
18
25
35
45
9
20
30
40

Sample Output 3

20

Sample Input 4

10 25
100 12
50 5
200 30
80 9
150 18
60 7
120 14
40 4
180 25
90 10
35
42
58
61
79
83
99
101
119
121
145
149
151
175
180
190
200
50
50
75
110
130
160
20
100

Sample Output 4

90

Sample Input 5

1 1
1000000000 1000000000
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi enjoys mountain climbing as a hobby and is interested in the "smoothness" of mountain paths.

Takahashi represents mountain paths as positive integers. Let the decimal representation of a positive integer X have k digits, and let the digits from the most significant digit (leftmost) to the least significant be d_1, d_2, \ldots, d_k. Takahashi regards these digits as elevation levels of k points arranged in a row from left to right. That is, the elevation level of the i-th point is d_i (an integer between 0 and 9, inclusive). Since X is a positive integer without leading zeros, d_1 is between 1 and 9, inclusive.

The sequence of elevation differences between adjacent points, listed in order,

e_1, e_2, \ldots, e_{k-1} \quad \text{where} \quad e_i = |d_i - d_{i+1}| \quad (1 \leq i \leq k-1)

is called the "step sequence of X". When k = 1 (i.e., X is a single-digit number), the step sequence is an empty sequence.

Takahashi calls a positive integer whose step sequence is monotonically non-decreasing a "smooth mountain path." Here, monotonically non-decreasing means that e_i \leq e_{i+1} holds for all 1 \leq i \leq k-2. Intuitively, this is a mountain path where the steps are small at the beginning of the walk and may become larger as you proceed, but never become smaller along the way. When X is a single-digit number (empty step sequence) or a two-digit number (step sequence with only one element), there is no i for which the condition must hold, so it is always a smooth mountain path.

Examples:

• The step sequence of X = 1234 is (|1-2|,\ |2-3|,\ |3-4|) = (1, 1, 1). Since 1 \leq 1 \leq 1, it is monotonically non-decreasing, so this is a smooth mountain path.
• The step sequence of X = 3152 is (|3-1|,\ |1-5|,\ |5-2|) = (2, 4, 3). Since there is a position where 4 > 3, this is not a smooth mountain path.

You are given positive integers L and R. Find the number of integers between L and R (inclusive) that are smooth mountain paths, modulo 10^9 + 7.

Constraints

• 1 \leq L \leq R < 10^{5000}
• L and R are given in decimal notation without leading zeros. Therefore, the number of digits of L and the number of digits of R are each at most 5000.

Sample Input 1

1
20

Sample Output 1

20

Sample Input 2

98
123

Sample Output 2

24

Sample Input 3

1000
50000

Sample Output 3

6624

Sample Input 4

123456789012345678901234567890
987654321098765432109876543210

Sample Output 4

426844825

Sample Input 5

1
1

Sample Output 5

1