Problem Statement

There is one humidifier in the AtCoder company office. The current time is 0, and the humidifier has no water inside.

You will add water to this humidifier N times. The i-th addition of water (1 \leq i \leq N) takes place at time T_i, and you add V_i liters of water. It is guaranteed that T_i < T_{i+1} for all 1 \leq i \leq N-1.

However, the humidifier has a leak, and as long as there is water inside, the amount of water decreases by 1 liter per unit time.

Find the amount of water remaining in the humidifier immediately after you finish adding water at time T_N.

Constraints

• 1 \leq N \leq 100
• 1 \leq T_i \leq 100 (1 \leq i \leq N)
• 1 \leq V_i \leq 100 (1 \leq i \leq N)
• T_i < T_{i+1} (1 \leq i \leq N-1)
• All input values are integers.

Sample Input 1

4
1 3
3 1
4 4
7 1

Sample Output 1

3

At each point in time, water is added as follows:

• Time 1: Before adding, the humidifier has 0 liters. After adding 3 liters, it has 3 liters.
• Time 3: Before adding, it has 1 liter. After adding 1 liter, it has 2 liters total.
• Time 4: Before adding, it has 1 liter. After adding 4 liters, it has 5 liters total.
• Time 7: Before adding, it has 2 liters. After adding 1 liter, it has 3 liters total.

After finishing the addition at time 7, the humidifier contains 3 liters. Thus, the answer is 3.

Sample Input 2

3
1 8
10 11
21 5

Sample Output 2

5

Sample Input 3

10
2 1
22 10
26 17
29 2
45 20
47 32
72 12
75 1
81 31
97 7

Sample Output 3

57

Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

• Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

• Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

• 2 \leq H, W \leq 100
• 1 \leq Q \leq 100
• For type 1 queries, 1 \leq R.
• When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
• For type 2 queries, 1 \leq C.
• When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
• All input values are integers.

Sample Input 1

7 9 5
2 4
1 3
2 1
2 1
1 3

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

• 1 x: Append x to the end of A.
• 2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

• 1 \leq Q \leq 100
• In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
• In the second type of query, k is a positive integer not greater than the current length of sequence A.

Sample Input 1

5
1 20
1 30
2 1
1 40
2 3

Sample Output 1

30
20

• Initially, A is empty.
• The first query appends 20 to the end of A, making A=(20).
• The second query appends 30 to the end of A, making A=(20,30).
• The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
• The fourth query appends 40 to the end of A, making A=(20,30,40).
• The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

Problem Statement

Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.

Currently, he has N head parts and M body parts. The weight of the i-th (1\le i\le N) head part is H _ i grams, and the weight of the i-th (1\le i\le M) body part is B _ i grams.

He wants to create a total of K robots that do not fall over by appropriately combining the parts he has. Determine whether he can achieve his goal by combining the parts well.

Here, a part cannot be used to create multiple robots, and two or more head parts (or two or more body parts) cannot be used to create one robot.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le M\le2\times10 ^ 5
• 1\le K\le\min\lbrace N,M\rbrace
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le B _ i\le10 ^ 9\ (1\le i\le M)
• All input values are integers.

Sample Input 1

6 6 3
2 7 1 8 2 8
1 8 2 8 4 5

Sample Output 1

Yes

If we denote combining the i-th head part and the j-th body part as (i,j), then Takahashi can create three robots that do not fall over by combining them as (1,2),(2,4),(3,6), for example.

Thus, print Yes.

Sample Input 2

1 1 1
43
1

Sample Output 2

No

His head part is too heavy, so he cannot create any robot that does not fall over.

Sample Input 3

1 1 1
100
100

Sample Output 3

Yes

Note that a robot does not fall over if the head and body have equal weights.

Sample Input 4

12 15 12
748 169 586 329 972 529 432 519 408 587 138 249
656 114 632 299 984 755 404 772 155 506 832 854 353 465 387

Sample Output 4

Yes