Problem Statement

Takahashi has just finished grading the school's final exam. N students took this exam, and each student is assigned an attendance number from 1 to N.

According to the school's regulations, students who scored K points or more on the exam pass and are exempt from the makeup exam. Students who scored less than K points fail and must take the makeup exam.

The score of the student with attendance number i is S_i points.

Takahashi wants to know the number of students who passed. Find the number of students who scored K points or more on the exam.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 100
• 0 \leq S_i \leq 100 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 60
72 45 60 88 59

Sample Output 1

3

Sample Input 2

10 50
100 49 50 0 75 50 33 82 51 48

Sample Output 2

6

Sample Input 3

20 70
65 70 82 55 91 70 43 88 69 71 100 0 45 78 62 95 70 68 84 50

Sample Output 3

11

Problem Statement

Takahashi set up a cheer message board at his school's cultural festival.

On this board, visitors can write cheer messages for the performers. Takahashi wants to count the number of "energetic cheer messages" in order to analyze the excitement of the cultural festival.

An "energetic cheer message" is a message whose string contains K or more exclamation marks !.

N visitors each wrote exactly one cheer message. Each visitor's message is given as a string consisting of lowercase English letters, uppercase English letters, digits, and exclamation marks. Determine how many "energetic cheer messages" there are.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 10^3
• 1 \leq |S_i| \leq 10^3 (|S_i| denotes the length of string S_i)
• S_i consists only of lowercase English letters (a–z), uppercase English letters (A–Z), digits (0–9), and exclamation marks (!) (no spaces are included)
• N, K are integers

Sample Input 1

3 2
Hello!
Great!!Work!!
Nice

Sample Output 1

1

Sample Input 2

5 3
Ganbare!!!
Good!Luck!
Wonderful!!!!!
Fight!
BestWishes!!!YouCanDoIt!!!

Sample Output 2

3

Sample Input 3

8 4
Amazing!Performance!
Bravo!!!!
You!Are!The!Best!
Super!!!
Fantastic!!!!!!!!
Keep!Going!
Excellent!Work!Everyone!Cheers!
WOW!!

Sample Output 3

4

Problem Statement

Takahashi is organizing a card game tournament.

The tournament uses N cards. Card i (1 \leq i \leq N) has a positive integer A_i written on it, and all integers written on the N cards are distinct.

Takahashi wants to divide all N cards into several groups. Each card must belong to exactly one group, and every group must contain at least one card. Furthermore, each group must be a "consecutive group" as defined below.

A set of cards is a consecutive group if the set of integers written on the cards in it can be expressed as \{a, a+1, a+2, \ldots, a+k-1\} for some integer a and positive integer k. In other words, it is a set consisting of k consecutive integers. When k = 1, i.e., a group consisting of just one card, it is also a consecutive group.

For example, a set of 3 cards with the integers 3, 5, 4 written on them forms the integer set \{3, 4, 5\}, which consists of 3 consecutive integers, so it is a consecutive group. On the other hand, a set of 3 cards with the integers 2, 4, 5 is not a consecutive group because 3 is missing between 2 and 4.

When dividing all N cards into consecutive groups, find the minimum number of groups.

Constraints

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

Sample Input 1

3
3 5 4

Sample Output 1

1

Sample Input 2

7
2 4 5 10 11 12 7

Sample Output 2

4

Sample Input 3

15
100 3 50 51 52 1 2 200 201 202 203 53 4 5 999999999

Sample Output 3

5

Problem Statement

Takahashi is the manager of a botanical garden. The garden contains N plants, each numbered from 1 to N.

Each plant i (1 \leq i \leq N) has an "ornamental value" A_i and a "drought resistance" B_i. Plants with higher ornamental value are more attractive to visitors, and plants with higher drought resistance are more resilient to water shortages.

An intense heatwave is expected this summer, and some plants may wither due to water shortage. Specifically, plants whose drought resistance B_i is at least the threshold T will survive without any intervention, but plants whose B_i is less than T will wither if no measures are taken.

To protect the plants that would wither, Takahashi has decided to install irrigation equipment on some plants. For each plant i, he chooses whether or not to install irrigation equipment. Irrigation equipment can be installed on any plant (including plants whose drought resistance is at least T), and it is also allowed to install none at all. However, at most one irrigation equipment can be installed per plant. Installing irrigation equipment on plant i costs C_i, and a plant with irrigation equipment installed will not wither regardless of its drought resistance value.

The total installation cost of the irrigation equipment must not exceed Takahashi's budget M.

In summary, plant i survives (does not wither) if it satisfies either (or both) of the following conditions:

• Irrigation equipment is installed on plant i
• Its drought resistance B_i is at least T

Plants that satisfy neither of these conditions will wither. Note that even if both conditions are satisfied simultaneously, the ornamental value is not counted twice.

Takahashi wants to maximize the total ornamental value of the surviving plants by choosing which plants to install irrigation equipment on, within the budget M.

Find the maximum possible sum of ornamental values A_i over all surviving plants.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 10^4
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^6
• 1 \leq B_i \leq 10^9
• 1 \leq C_i \leq 10^4
• All input values are integers

Sample Input 1

3 100 50
80 30 60
50 60 40
30 40 50

Sample Output 1

130

Sample Input 2

5 200 100
100 50 80
200 150 120
150 80 90
50 200 30
80 90 70

Sample Output 2

500

Sample Input 3

10 500 1000
500 800 100
300 1200 80
450 500 150
200 2000 50
150 900 120
600 600 200
100 1500 40
350 400 180
250 1100 90
400 700 160

Sample Output 3

2400

Problem Statement

Takahashi is trying to stack cardboard boxes onto a truck bed for moving.

Takahashi has N cardboard boxes, where the i-th box has weight W_i and load capacity D_i. He selects some of these boxes (possibly 0, but each box can be selected at most once) and stacks the selected boxes in a single column from bottom to top in any order he likes.

However, there is a load capacity constraint on the boxes. If the total weight of all boxes placed on top of a given box exceeds that box's load capacity (i.e., is strictly greater than the load capacity), that box will be crushed. If the total weight is at most the load capacity, the box will not be crushed. If even one box is crushed, the stacking is not valid.

Takahashi wants to select and stack boxes so that the stacking is valid. Maximize the number of boxes used in the stacking.

More precisely: select a subset S from the N boxes (S may be empty). Stack the boxes in S in some order in a single column from bottom to top. The stacking is said to be valid if, for every box in S, the total weight of all boxes above it is at most that box's load capacity. A subset S is said to be feasible if there exists at least one ordering of the boxes in S such that the stacking is valid. Find the maximum value of |S| among all feasible subsets S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9
• 0 \leq D_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 5
2 3
4 2

Sample Output 1

2

Sample Input 2

5
1 100
2 50
3 20
1 10
2 5

Sample Output 2

5

Sample Input 3

8
10 90
20 70
30 50
40 30
50 10
100 0
5 1000000000
1000000000 0

Sample Output 3

5