Problem Statement

Takahashi is picking apples in an orchard.

There are N apple trees lined up in a row in the orchard, numbered tree 1, tree 2, \ldots, tree N from left to right. Tree i has D_i apples on it.

Takahashi starts from tree 1 and proceeds to the right, harvesting apples according to the following pattern:

• Harvest apples from K consecutive trees (for each tree he harvests, he picks all the apples on that tree).
• Immediately after, he skips 1 tree without harvesting, as he is tired and takes a rest.

He repeats this pattern starting from tree 1 until he reaches tree N. If he reaches tree N in the middle of a pattern, he stops there. Takahashi cannot freely choose which trees to harvest or the order in which to harvest them.

Find the total number of apples Takahashi harvests.

For example, when N = 7, K = 3, Takahashi harvests from trees 1, 2, 3, skips tree 4, and harvests from trees 5, 6, 7.

Also, when N = 8, K = 2, Takahashi harvests from trees 1, 2, skips tree 3, harvests from trees 4, 5, skips tree 6, and harvests from trees 7, 8.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq K \leq N
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

7 3
5 3 2 8 4 1 6

Sample Output 1

21

Sample Input 2

8 2
3 1 4 1 5 9 2 6

Sample Output 2

18

Sample Input 3

15 4
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150

Sample Output 3

900

Sample Input 4

20 3
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

Sample Output 4

750

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi and Aoki have each finished moving and started living in a new town. They want to find the nearest post office from where they live and register for its services.

This town can be represented as a number line with a single road, and there are N post offices scattered along the road. The i-th post office is located at coordinate X_i and currently has C_i registered users. Note that the post offices are not necessarily ordered by coordinate.

Takahashi lives at coordinate P, and Aoki lives at coordinate Q. Each of them independently registers at the post office closest to where they live. Here, the distance between a person's residence and a post office is measured as the absolute difference of their coordinates. If there are multiple closest post offices, they choose the one with the smallest coordinate.

As a result of each person's registration, the number of registered users at their chosen post office increases by 1. If both register at the same post office, the number of registered users at that post office increases by 2.

After both registrations are complete, let S be the set of post offices where Takahashi and Aoki registered (if both registered at the same post office, S contains that post office only once). For each post office in S, determine the number of registered users after registration is complete, and output the total.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq P \leq 10^9
• -10^9 \leq Q \leq 10^9
• -10^9 \leq X_i \leq 10^9
• 0 \leq C_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All inputs are integers

Sample Input 1

3 5 15
0 10
10 20
20 30

Sample Output 1

32

Sample Input 2

4 0 0
-5 100
5 200
3 50
-3 80

Sample Output 2

82

Sample Input 3

5 -1000000000 1000000000
0 500000000
-999999999 100
1000000000 300000000
-500000000 200000000
500000000 150000000

Sample Output 3

300000102

Problem Statement

Takahashi is working a part-time job at a moving company. At today's site, there are N packages and N carts.

The weight of package i (1 \leq i \leq N) is W_i, and the weight capacity of cart j (1 \leq j \leq N) is C_j. To place package i on cart j, the weight of the package must not exceed the weight capacity of the cart, i.e., W_i \leq C_j.

Each cart can hold at most 1 package, and each package can be placed on at most 1 cart. It is acceptable to have packages not placed on any cart, or carts with no packages.

Takahashi wants to load as many packages as possible onto the carts for transport. Find the maximum number of packages that can be loaded onto carts and transported.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq N)
• All inputs are integers.

Sample Input 1

4
3 5 2 8
4 7 1 6

Sample Output 1

3

Sample Input 2

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Sample Output 2

7

Sample Input 3

10
5 12 8 3 15 20 7 1 9 50
10 6 25 2 4 14 8 30 3 11

Sample Output 3

9

Problem Statement

Takahashi wants to repeatedly add and remove elements from a multiset of integers (a set that can contain multiple copies of the same value), and count how many removals satisfy a certain condition.

Initially, the multiset is empty. You are given Q queries in order, of the following 2 types. Let X_i denote the value specified by the i-th query.

• + X_i: Add one copy of the value X_i to the multiset.
• - X_i: Remove one copy of the value X_i from the multiset. It is guaranteed that at least one copy of the value X_i exists in the multiset at this point.

For a removal query, if the value X_i being removed matches the median of the multiset immediately before the removal, this removal is called a "median hit".

Here, the median of a multiset with n elements (n \geq 1) is defined as follows: when all elements are sorted in ascending order, the \lceil n/2 \rceil-th value (1-indexed) is the median. In other words, when the number of elements is odd, it is the middle value; when even, it is the smaller of the two middle values.

Since the multiset contains at least one element at the time of a removal query, the median is always well-defined.

Process all queries in order and determine the number of times a "median hit" occurs.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 1 \leq X_i \leq 10^9
• At the time a - X_i query is given, at least one copy of the value X_i exists in the multiset.
• All numerical values given in the input are integers.

Sample Input 1

6
+ 1
+ 3
+ 2
- 2
- 1
- 3

Sample Output 1

3

Sample Input 2

8
+ 10
+ 20
- 20
+ 15
+ 25
- 25
- 10
- 15

Sample Output 2

2

Sample Input 3

15
+ 5
+ 1
+ 5
+ 3
+ 3
- 3
+ 4
- 5
+ 2
- 3
+ 5
- 4
- 5
- 1
- 2

Sample Output 3

4

Sample Input 4

25
+ 1000000000
+ 7
+ 7
+ 500
+ 8
- 7
+ 6
- 8
+ 9
+ 10
- 7
+ 9
- 9
+ 1
- 6
+ 2
+ 3
- 9
+ 4
- 4
- 1000000000
- 3
- 1
- 10
- 2

Sample Output 4

7

Sample Input 5

1
+ 1000000000

Sample Output 5

0

Problem Statement

Takahashi has N types of chemicals. The i-th chemical has two modes of use: normal mode and heated mode. Using it in normal mode yields A_i mL of solution, and using it in heated mode yields B_i mL of solution.

From these chemicals, Takahashi selects some (possibly zero) of them, and for each selected chemical, independently decides whether to use it in normal mode or heated mode. Each chemical can be used at most once. Determine whether it is possible for the total amount of solution obtained from the selected chemicals to be exactly K mL.

If it is possible, output Yes; if it is impossible, output No.

Constraints

• 1 \leq N \leq 26
• 0 \leq K \leq 10^{15}
• 1 \leq A_i \leq 10^{14}
• 1 \leq B_i \leq 10^{14}
• All input values are integers.

Sample Input 1

3 10
3 5
4 6
1 8

Sample Output 1

Yes

Sample Input 2

2 5
2 4
6 8

Sample Output 2

No

Sample Input 3

8 57
11 14
7 10
9 15
13 20
17 18
6 16
8 12
5 21

Sample Output 3

Yes

Sample Input 4

20 590000000000000
10000000000000 11000000000000
12000000000000 13000000000000
14000000000000 15000000000000
16000000000000 17000000000000
18000000000000 19000000000000
20000000000000 21000000000000
22000000000000 23000000000000
24000000000000 25000000000000
26000000000000 27000000000000
28000000000000 29000000000000
30000000000000 31000000000000
32000000000000 33000000000000
34000000000000 35000000000000
36000000000000 37000000000000
38000000000000 39000000000000
40000000000000 41000000000000
42000000000000 43000000000000
44000000000000 45000000000000
46000000000000 47000000000000
48000000000000 49000000000000

Sample Output 4

Yes

Sample Input 5

1 0
1 100000000000000

Sample Output 5

Yes