A - Content Too Large

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんは、N 個の品物と 1 つのカバンを持っています。

i 番目 (1\le i\le N) の品物の大きさは A _ i で、カバンの大きさは M です。

カバンに入れようとしている品物の大きさの合計が M 以下のとき、かつそのときに限り、それらの品物をすべて同時にカバンに入れることができます。

高橋くんが N 個の品物すべてを同時にカバンに入れることができるなら Yes 、そうでなければ No と出力してください。

制約

  • 1\le N\le100
  • 1\le M\le10000
  • 1\le A _ i\le100\ (1\le i\le N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A _ 1 A _ 2 \ldots A _ N

出力

高橋くんがすべての品物を同時にカバンに入れられるなら Yes を、そうでなければ No を出力せよ。


入力例 1

5 15
3 1 4 1 5

出力例 1

Yes

5 つの品物の大きさの合計は 3+1+4+1+5=14 です。 これは、カバンの大きさ 15 以下なので、高橋くんはすべての品物を同時にカバンに入れることができます。 なので、Yes を出力してください。


入力例 2

5 5
3 1 4 1 5

出力例 2

No

5 つの品物の大きさの合計は 14 で、カバンの大きさ 5 より大きいため、高橋くんはすべての品物を同時にカバンに入れることができません。 なので、No を出力してください。


入力例 3

1 10000
100

出力例 3

Yes

Score : 100 points

Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

  • 1\le N\le100
  • 1\le M\le10000
  • 1\le A_i\le100\ (1\le i\le N)
  • All input values are integers.

Input

The input is given from standard input in the following format:

N M
A_1 A_2 \ldots A_N

Output

If Takahashi can put all items in the bag simultaneously, print Yes; otherwise, print No.


Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.


Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.


Sample Input 3

1 10000
100

Sample Output 3

Yes
B - September

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる 12 個の文字列 S_1,S_2,\ldots,S_{12} があります。

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか求めてください。

制約

  • S_i は英小文字からなる長さ 1 以上 100 以下の文字列である。(1 \leq i \leq 12)

入力

入力は以下の形式で標準入力から与えられる。

S_1
S_2
\vdots
S_{12}

出力

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか出力せよ。


入力例 1

january
february
march
april
may
june
july
august
september
october
november
december

出力例 1

1

S_i の長さが i であるような整数 i は 9 の 1 つのみです。よって、1 と出力します。


入力例 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

出力例 2

2

S_i の長さが i であるような整数 i は 4,8 の 2 つです。よって、2 と出力します。

Score : 100 points

Problem Statement

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

  • Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Input

The input is given from Standard Input in the following format:

S_1
S_2
\vdots
S_{12}

Output

Print the number of integers i (1 \leq i \leq 12) such that the length of S_i is i.


Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.


Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

C - Pepper Addiction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君はコショウが大好きです。

M 種類のコショウがレストランに置いてあり、それぞれを種類 1,2,\dots,M と呼びます。 このレストランに種類 j ( 1 \le j \le M ) のコショウは C_j g だけあります。

高橋君はこの店で N 個の料理を注文しました。
相性の都合で i ( 1 \le i \le N ) 番目の料理には種類 A_i のコショウしかかけることができず、 i 番目の料理にかけられるコショウの量の上限は B_i g です。
また、高橋君がこれらの料理にかけられるのはレストランに置いてあるコショウのみです。つまり、種類 j のコショウを合計 C_j g を超えてかけることはできません。

高橋君は、料理にかけたコショウの量の合計を最大にするようにどの料理にどれだけのコショウをかけるかを決めます。
このとき、高橋君は合計何 g のコショウを料理にかけることができますか?

制約

  • 入力は全て整数
  • 1 \le N,M \le 1000
  • 1 \le A_i \le M
  • 1 \le B_i,C_i \le 10^6

入力

入力は以下の形式で標準入力から与えられる。

N M
C_1 C_2 \dots C_M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを整数として出力せよ。


入力例 1

7 5
4 4 8 3 7
1 2
2 3
5 2
4 10
2 3
5 4
2 3

出力例 1

15

この入力では 5 種類のコショウがあり、種類 1,2,3,4,5 のコショウがそれぞれ 4,4,8,3,7 g あります。
以下のようにすると料理にかけたコショウの量の合計が 15 g となり、これが達成可能な最大です。

  • 1 番目の料理に種類 1 のコショウを 2 g かける。
  • 2 番目の料理にはコショウをかけない。
  • 3 番目の料理に種類 5 のコショウを 2 g かける。
  • 4 番目の料理に種類 4 のコショウを 3 g かける。
  • 5 番目の料理に種類 2 のコショウを 1 g かける。
  • 6 番目の料理に種類 5 のコショウを 4 g かける。
  • 7 番目の料理に種類 2 のコショウを 3 g かける。

入力例 2

1 1
1
1 1

出力例 2

1

入力例 3

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

出力例 3

438

Score : 200 points

Problem Statement

Takahashi loves pepper.

A restaurant has M types of pepper, called type 1,2,\dots,M. There are C_j grams of type j (1 \le j \le M) pepper at this restaurant.

He ordered N dishes at this restaurant.
Due to compatibility, only type A_i pepper can be sprinkled on dish i (1 \le i \le N), and the upper limit on the amount of pepper that can be sprinkled on dish i is B_i grams.
Also, he can only use the pepper available at the restaurant. That is, the total amount of type j pepper sprinkled cannot exceed C_j grams.

He decides how much pepper to sprinkle on each dish to maximize the total amount of pepper sprinkled on the dishes.
How many grams of pepper in total can he sprinkle on the dishes?

Constraints

  • All input values are integers.
  • 1 \le N,M \le 1000
  • 1 \le A_i \le M
  • 1 \le B_i,C_i \le 10^6

Input

The input is given from Standard Input in the following format:

N M
C_1 C_2 \dots C_M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer as an integer.


Sample Input 1

7 5
4 4 8 3 7
1 2
2 3
5 2
4 10
2 3
5 4
2 3

Sample Output 1

15

In this input, there are five types of pepper, with 4,4,8,3,7 grams of type 1,2,3,4,5 pepper respectively.
The following gives a total of 15 grams of pepper sprinkled on the dishes, which is the maximum achievable.

  • Sprinkle 2 grams of type 1 pepper on dish 1.
  • Sprinkle no pepper on dish 2.
  • Sprinkle 2 grams of type 5 pepper on dish 3.
  • Sprinkle 3 grams of type 4 pepper on dish 4.
  • Sprinkle 1 gram of type 2 pepper on dish 5.
  • Sprinkle 4 grams of type 5 pepper on dish 6.
  • Sprinkle 3 grams of type 2 pepper on dish 7.

Sample Input 2

1 1
1
1 1

Sample Output 2

1

Sample Input 3

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

Sample Output 3

438
D - Frequency

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S に最も多く出現する文字を求めてください。そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えてください。

制約

  • 1 \leq |S| \leq 1000(|S| は文字列 S の長さ)
  • S の各文字は英小文字である。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S に最も多く出現する文字のうちアルファベット順で最も早いものを出力せよ。


入力例 1

frequency

出力例 1

e

frequency には e が 2 回出現し、これは他のどの文字よりも多いため e を出力します。


入力例 2

atcoder

出力例 2

a

atcoder には a, t, c, o, d, e, r が 1 回ずつ出現するため、このうちアルファベット順で最も早い a を出力します。


入力例 3

pseudopseudohypoparathyroidism

出力例 3

o

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.

Constraints

  • 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
  • Each character in S is a lowercase English letter.

Input

The input is given from Standard Input in the following format:

S

Output

Among the characters that appear most frequently in S, print the one that comes earliest in alphabetical order.


Sample Input 1

frequency

Sample Output 1

e

In frequency, the letter e appears twice, which is more than any other character, so you should print e.


Sample Input 2

atcoder

Sample Output 2

a

In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.


Sample Input 3

pseudopseudohypoparathyroidism

Sample Output 3

o
E - LRUD Instructions 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面上に高橋君がいます。高橋君は原点から移動を N 回行いました。

N 回の移動は長さ N の文字列で表され、意味は次の通りです。

  • i 回目の高橋君の移動後の座標は、移動前の座標を (x,y) として、
    • S の i 文字目が R であるとき (x+1,y)
    • S の i 文字目が L であるとき (x-1,y)
    • S の i 文字目が U であるとき (x,y+1)
    • S の i 文字目が D であるとき (x,y-1)

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあるかどうかを判定してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • N は整数
  • S は R, L, U, D のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあれば Yes、なければ No と出力せよ。


入力例 1

5
RLURU

出力例 1

Yes

高橋君のいる座標は (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2) と変化します。


入力例 2

20
URDDLLUUURRRDDDDLLLL

出力例 2

No

Score : 300 points

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

  • Takahashi's coordinates after the i-th move are:

    • (x+1,y) if the i-th character of S is R;
    • (x-1,y) if the i-th character of S is L;
    • (x,y+1) if the i-th character of S is U; and
    • (x,y-1) if the i-th character of S is D,

    where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

  • 1 \leq N \leq 2\times 10^5
  • N is an integer.
  • S is a string of length N consisting of R, L, U, and D.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print Yes if Takahashi visited the same coordinates multiple times in the course of the N moves; print No otherwise.


Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).


Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No