Problem Statement

Takahashi is in charge of quality control at a factory. This factory manufactures N types of products, each numbered from 1 to N.

Each product has two metrics: a "quality index" and a "production quantity." The quality index of product i is A_i, and its daily production quantity is B_i units. A higher quality index indicates that defective items are more likely to occur.

Takahashi decided to calculate a "risk score" for each product. The risk score of product i is defined as the product of the quality index A_i and the production quantity B_i, namely A_i \times B_i. A higher risk score means that more attention is required for that product.

Takahashi believes that products with a risk score of K or higher need to be prioritized for improvement. Find the number of products whose risk score is K or higher.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq 100 (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers.

Sample Input 1

3 100
10 5
20 10
5 30

Sample Output 1

2

Sample Input 2

5 500
15 40
8 100
50 20
30 15
25 25

Sample Output 2

4

Problem Statement

Takahashi is observing an interesting phenomenon at a party venue.

N participants are standing in a line, all facing the same direction (to the right), and are numbered 1, 2, \ldots, N from left to right. Each participant is wearing a glove on their left hand and right hand (from their own perspective). The color of each glove is either navy or white. In the input, navy is represented by N (Navy) and white is represented by S (Snow).

> Note: The character N representing the navy color and the integer N representing the number of participants are different things. Please be careful not to confuse them.

The color of participant i's left-hand glove is given as L_i, and the color of their right-hand glove is given as R_i.

Since all participants are standing in a line facing the same direction, when two adjacent participants shake hands, the right hand of the left participant (the one with the smaller number) and the left hand of the right participant (the one with the larger number) touch each other. If the colors of the two gloves that touch are the same (both navy or both white), this is called an awkward handshake.

Takahashi wants to know the number of adjacent participant pairs that result in an awkward handshake.

Specifically, for each i = 1, 2, \ldots, N-1, check whether the color of participant i's right-hand glove R_i and the color of participant i+1's left-hand glove L_{i+1} are the same, and find the number of such i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• L_i is N or S (1 \leq i \leq N)
• R_i is N or S (1 \leq i \leq N)

Sample Input 1

4
N S
S N
N N
S S

Sample Output 1

2

Sample Input 2

2
N N
N S

Sample Output 2

1

Sample Input 3

10
S S
S N
N S
S S
S N
N N
N S
S S
S N
N N

Sample Output 3

9

Problem Statement

Takahashi will purchase all N items, one of each.

Each item has two prices: a "regular price" and a "sale price." The regular price of item i (1 \leq i \leq N) is A_i yen, and the sale price is B_i yen. It is guaranteed that the sale price is at most the regular price, that is, B_i \leq A_i.

Takahashi has one special discount coupon. With this coupon, he can choose at most K items from the N items and purchase the chosen items at their sale prices. The remaining items that are not chosen will be purchased at their regular prices. Note that the same item cannot be chosen more than once, and it is also allowed to choose no items (i.e., choose 0 items).

When Takahashi optimally chooses which items to purchase at the sale price, find the minimum possible total cost of purchasing all N items.

Constraints

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

Sample Input 1

3 2
100 80
200 150
300 250

Sample Output 1

500

Sample Input 2

5 3
1000 500
800 800
600 400
900 700
1200 300

Sample Output 2

2900

Sample Input 3

7 4
500000000 100000000
300000000 250000000
800000000 200000000
150000000 150000000
600000000 350000000
400000000 100000000
700000000 650000000

Sample Output 3

1900000000

Problem Statement

Takahashi is the manager of the track and field club, and he manages the practice records of the club members.

The track and field club has a practice period of N days, and each day is numbered from 1 to N. On day i (1 \leq i \leq N), a positive integer A_i representing the "practice intensity" for that day is recorded.

According to the club's rules, a period consisting of r - l + 1 consecutive days from day l to day r is called an "achievement period" and is specially recognized if its length is at least K days and the total practice intensity within the period is at least the target value M.

Takahashi wants to find out how many achievement periods qualify for recognition.

Specifically, find the number of integer pairs (l, r) that satisfy all of the following conditions:

• 1 \leq l \leq r \leq N
• r - l + 1 \geq K (the length of the period is at least K days)
• A_l + A_{l+1} + \cdots + A_r \geq M (the total practice intensity within the period is at least M)

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq M \leq 10^{14}
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

5 2 10
3 5 4 2 6

Sample Output 1

6

Sample Input 2

8 3 15
2 4 6 3 5 7 1 8

Sample Output 2

17

Sample Input 3

10 4 1000000000000
500000000 600000000 400000000 300000000 700000000 200000000 800000000 100000000 900000000 550000000

Sample Output 3

0

Problem Statement

Takahashi works at a shipping company. Today, he needs to deliver N packages from the distribution center to their destinations. Each package is numbered from 1 to N, and package i weighs W_i kilograms.

The distribution center has M trucks, each numbered from 1 to M. Truck j has a maximum load capacity of C_j kilograms, meaning the total weight of packages loaded onto that truck must not exceed C_j kilograms. There is no limit on the number of packages loaded onto each truck, and it is acceptable for a truck to carry no packages at all.

Each package cannot be split and must be loaded onto exactly one truck. Determine whether it is possible to load all N packages onto the trucks without exceeding any truck's maximum load capacity.

Constraints

• 1 \leq N \leq 15
• 1 \leq M \leq 15
• 1 \leq W_i \leq 10^8 (1 \leq i \leq N)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

3 2
3 5 2
6 4

Sample Output 1

No

Sample Input 2

4 2
10 20 30 40
50 50

Sample Output 2

Yes

Sample Input 3

8 3
15 25 30 10 20 35 5 40
80 60 50

Sample Output 3

Yes