Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

• Among the digits of N, the digit 1 appears exactly once.
• Among the digits of N, the digit 2 appears exactly twice.
• Among the digits of N, the digit 3 appears exactly three times.

Constraints

• N is an integer satisfying 100000 \le N \le 999999.

Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No

Problem Statement

The following five days are called the five seasonal festivals (gosekku).

• January \color{red}{\mathbf{7}}
• March 3
• May 5
• July 7
• September 9

If month M, day D is one of the five seasonal festivals, output Yes; otherwise, output No.

Constraints

• M and D are integers.
• Month M, day D is a valid date in a leap year in the Gregorian calendar.

Sample Input 1

3 3

Sample Output 1

Yes

March 3 is one of the five seasonal festivals, so output Yes.

Sample Input 2

1 1

Sample Output 2

No

January 1 is not one of the five seasonal festivals, so output No.

Sample Input 3

4 4

Sample Output 3

No

Sample Input 4

11 7

Sample Output 4

No

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

• All input values are integers.
• 1 \le M \le 100
• 1 \le D_i \le 100
• D_1 + D_2 + \dots + D_M is odd.

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

• Months 1,2,3,4,5,6 contain a total of 181 days.
• Day 1 of month 7 is the 182-th day.
• Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

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

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

Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.