Problem Statement

Takahashi works at a library. On a bookshelf in the library, N books are lined up in a row, and each book has a catalog number assigned to it. The catalog number of the i-th book from the left (1 \leq i \leq N) is A_i. Note that different books may have the same catalog number.

Aoki asks, "I'm looking for the book with catalog number K. Where is it?"

Among the N books on the bookshelf, find the book whose catalog number is exactly K. If a book with catalog number K exists, output the smallest position of such a book (counted from the left, 1-indexed). If no such book exists, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3
1 4 3 2 3

Sample Output 1

3

Sample Input 2

7 100
50 200 100 100 300 100 400

Sample Output 2

3

Sample Input 3

10 999999999
1 1000000000 500000000 123456789 999999999 999999999 777777777 888888888 999999999 1

Sample Output 3

5

Problem Statement

Takahashi is in charge of shipping fruits harvested at a farm.

N fruits have been harvested at the farm, each numbered from 1 to N. For each fruit i (1 \leq i \leq N), a sweetness level A_i has been measured; the higher this value, the sweeter and more delicious the fruit.

It was discovered that M fruits have bruises. The numbers of the bruised fruits are given as B_1, B_2, \ldots, B_M (the order has no special meaning).

Normally, bruised fruits are shipped as substandard products through a separate route from the regular one. However, fruits with a sweetness level of K or higher (i.e., A_i \geq K) are treated specially as premium products, so even if they have bruises, they are not classified as substandard and are included in the regular shipping route.

In summary, fruits that have bruises and have a sweetness level less than K are shipped as substandard products.

Find the number of fruits that Takahashi should ultimately ship as substandard products, and the total sweetness level of those fruits.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq N
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq N (1 \leq j \leq M)
• B_1, B_2, \ldots, B_M are all distinct
• All inputs are integers

Sample Input 1

5 3 10
8 12 5 15 7
1 3 4

Sample Output 1

2 13

Sample Input 2

8 5 20
25 18 30 12 8 22 15 19
2 4 5 6 8

Sample Output 2

4 57

Sample Input 3

15 7 100
150 80 95 200 45 120 75 180 90 60 110 55 130 85 70
3 5 7 9 10 12 14

Sample Output 3

7 505

Problem Statement

Takahashi is conducting an experiment growing N types of plants in his school science class.

Each plant has a different initial height and daily growth rate. Specifically, the i-th plant (1 \leq i \leq N) has a height of A_i cm at the start of the experiment (day 0) and grows by B_i cm per day. That is, the height of the i-th plant on day d (d = 0, 1, 2, \ldots) is A_i + B_i \times d cm.

Takahashi plans to check the heights of the plants every day on day 0, day 1, day 2, \ldots, and end the observation on the first day when all plants have a height of at least M cm.

Find the day when the observation ends, that is, the smallest non-negative integer d such that A_i + B_i \times d \geq M holds for all i (1 \leq i \leq N).

Note that under the given constraints, the answer is guaranteed to exist as a finite value.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All input values are integers

Sample Input 1

3 10
2 3
5 2
8 1

Sample Output 1

3

Sample Input 2

4 100
100 5
90 10
95 3
80 4

Sample Output 2

5

Sample Input 3

5 1000000000
1 1
500000000 100000000
999999999 1
100000000 300000000
250000000 250000000

Sample Output 3

999999999

Problem Statement

After a long adventure, Takahashi has reached ruins containing N treasure chests.

Each treasure chest i (1 \leq i \leq N) is secured with a lock of strength C_i. A larger strength value means a sturdier lock. All treasure chests have mutually distinct lock strengths.

Takahashi has M keys. Each key j (1 \leq j \leq M) has an unlocking power R_j. Key j can open treasure chest i only if the key's unlocking power is at least as large as the lock's strength, that is, when C_i \leq R_j. Note that different keys may have the same unlocking power.

Takahashi selects some treasure chests he wants to open (possibly 0), and assigns exactly one key to each selected treasure chest to open it. However, the same key cannot be assigned to two or more treasure chests. Additionally, the key assigned to each treasure chest must be able to open it (C_i \leq R_j). It is fine to leave some keys unused or some treasure chests unopened.

Find the maximum number of treasure chests Takahashi can open.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
• C_i \neq C_k (i \neq k) (all lock strengths are mutually distinct)
• All input values are integers

Sample Input 1

3 3
10 20 30
15 25 35

Sample Output 1

3

Sample Input 2

5 3
100 200 300 400 500
150 250 450

Sample Output 2

3

Sample Input 3

7 10
50 120 80 200 350 500 1000
40 60 100 100 150 200 300 400 600 1500

Sample Output 3

7

Problem Statement

Takahashi found N kinds of sweets at a candy shop. The price of the i-th (1 \leq i \leq N) sweet is A_i yen. Since there is only one of each sweet in stock, for each sweet he must choose either "buy" or "don't buy." Note that different kinds of sweets may have the same price, but they are still distinguished as different sweets.

Takahashi has exactly S yen. Since he wants to make the most of it, he would like to buy sweets that cost exactly S yen in total, without leaving any money.

Among all ways to select 0 or more sweets from the N kinds, find the number of ways such that the total price of the selected sweets is exactly S yen. Note that if no sweets are selected, the total price is considered to be 0 yen.

Constraints

• 1 \leq N \leq 40
• 0 \leq S \leq 10^{12}
• 1 \leq A_i \leq 10^{12}
• All inputs are integers

Sample Input 1

4 10
2 3 5 7

Sample Output 1

2

Sample Input 2

6 15
1 2 4 5 8 10

Sample Output 2

4

Sample Input 3

10 1000000000000
100000000000 200000000000 300000000000 400000000000 500000000000 600000000000 700000000000 800000000000 900000000000 1000000000000

Sample Output 3

10