A - Anyway Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c, d が与えられるので、以下の指示に従って 2 行出力してください。

1 行目は (a + b) \times (c - d) の計算結果を整数として出力してください。
2 行目は入力にかかわらず Takahashi と出力してください。

制約

  • -100 \leq a, b, c, d \leq 100
  • a,b,c,d は整数

入力

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

a b c d 

出力

問題文の指示に従って 2 行出力せよ。


入力例 1

1 2 5 3

出力例 1

6
Takahashi

(1 + 2) \times(5 - 3) = 3 \times 2 = 6 です。よって 1 行目は 6 を出力します。
2 行目は Takahashi を出力します。1 文字目を小文字にしたりスペルを誤ったりすると誤答となるので注意してください。


入力例 2

10 -20 30 -40

出力例 2

-700
Takahashi

入出力に負の数が含まれる場合もあります。


入力例 3

100 100 100 -100

出力例 3

40000
Takahashi

Score : 100 points

Problem Statement

You are given integers a, b, c, and d. Print two lines as follows.

The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.

Constraints

  • -100 \leq a, b, c, d \leq 100
  • a, b, c, and d are integers.

Input

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

a b c d 

Output

Print two lines according to the Problem Statement.


Sample Input 1

1 2 5 3

Sample Output 1

6
Takahashi

We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.


Sample Input 2

10 -20 30 -40

Sample Output 2

-700
Takahashi

The input or output may contain negative numbers.


Sample Input 3

100 100 100 -100

Sample Output 3

40000
Takahashi
B - Distinct Strings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字のみからなる長さ 3 の文字列 S が与えられます。

S の各文字を並び替えて得られる文字列は、何種類ありますか?

制約

  • S は英小文字のみからなる長さ 3 の文字列

入力

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

S

出力

S の各文字を並び替えて得られる文字列の種類数を出力せよ。


入力例 1

aba

出力例 1

3

S= aba の各文字を並び替えて得られる文字列は、aab, aba, baa の 3 通りです。


入力例 2

ccc

出力例 2

1

S= ccc の各文字を並び替えて得られる文字列は、ccc の 1 通りのみです。


入力例 3

xyz

出力例 3

6

S= xyz の各文字を並び替えて得られる文字列は、xyz, xzy, yxz, yzx, zxy, zyx の 6 通りです。

Score : 100 points

Problem Statement

You are given a string S of length 3 consisting of lowercase English letters.

How many different strings can be obtained by permuting the characters in S?

Constraints

  • S is a string S of length 3 consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of different strings that can be obtained by permuting the characters in S.


Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.


Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.


Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.

C - Round-Robin Tournament

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号が付いた N 人のプレイヤーが総当たり戦をしました。この総当たり戦で行われた試合全てについて、二人の一方が勝ち、もう一方が負けました。

総当たり戦の結果は N 個の長さ N の文字列 S_1,S_2,\ldots,S_N によって以下の形式で与えられます。

  • i\neq j のとき、S_i の j 文字目は o, x のいずれかであり、o のときプレイヤー i がプレイヤー j に勝ったことを、x のときプレイヤー i がプレイヤー j に負けたことを意味する。

  • i=j のとき、S_i の j 文字目は - である。

総当たり戦で勝った試合数が多いほうが順位が上であり、勝った試合数が同じ場合は、プレイヤーの番号が小さいほうが順位が上となります。 N 人のプレイヤーの番号を順位が高い順に答えてください。

制約

  • 2\leq N\leq 100
  • N は整数
  • S_i は o, x, - からなる長さ N の文字列
  • S_1,\ldots,S_N は問題文中の形式を満たす

入力

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

N 
S_1
S_2
\vdots
S_N

出力

N 人のプレイヤーの番号を、順位が高い順に空白区切りで出力せよ。


入力例 1

3
-xx
o-x
oo-

出力例 1

3 2 1

プレイヤー 1 は 0 勝、プレイヤー 2 は 1 勝、プレイヤー 3 は 2 勝なので、プレイヤーの番号は順位が高い順に 3,2,1 です。


入力例 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

出力例 2

4 7 3 1 5 2 6

プレイヤー 4 とプレイヤー 7 はどちらも 5 勝ですが、プレイヤー番号が小さいプレイヤー 4 のほうが順位が上になります。

Score : 200 points

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

  • If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

  • If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

  • 2\leq N\leq 100
  • N is an integer.
  • S_i is a string of length N consisting of o, x, and -.
  • S_1,\ldots,S_N conform to the format described in the problem statement.

Input

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

N 
S_1
S_2
\vdots
S_N

Output

Print the player numbers of the N players in descending order of rank.


Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.


Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

D - Triple Metre

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S が文字列 T の部分文字列であるとは、次の条件を満たすような整数 i, j (1 \leq i \leq j \leq |T|) が存在することを言います。

  • T の i 文字目から j 文字目までを順番を変えずに抜き出してできる文字列が S と一致する。

文字列 T を oxx を 10^5 個結合した文字列として定めます。
文字列 S が与えられるので、 S が T の部分文字列である場合は Yes を、そうでない場合は No を出力してください。

制約

  • S は o と x のみからなる文字列である。
  • S の長さは 1 以上 10 以下である。

入力

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

S

出力

S が条件を満たす場合は Yes を、そうでない場合は No を出力せよ。


入力例 1

xoxxoxxo

出力例 1

Yes

T のはじめの方を抜き出すと oxxoxxoxxoxx... となっています。
T の 3 文字目から 10 文字目までを抜き出した文字列は S と一致するので、 S は T の部分文字列です。よって Yes を出力します。


入力例 2

xxoxxoxo

出力例 2

No

T から文字列をどのように抜き出しても S と一致しないので、S は T の部分文字列でありません。よって No を出力します。


入力例 3

ox

出力例 3

Yes

Score : 200 points

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

  • The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

  • S is a string consisting of o and x.
  • The length of S is between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

S

Output

If S satisfies the condition, print Yes; otherwise, print No.


Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.


Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.


Sample Input 3

ox

Sample Output 3

Yes
E - Graph Isomorphism

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君と青木君は、それぞれ N 個のボールに M 本のひもを取り付けたおもちゃを持っています。

高橋君のおもちゃにおいて、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール A_i とボール B_i を結んでいます。

青木君のおもちゃにおいても同様に、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール C_i とボール D_i を結んでいます。

それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2 つのボールを 2 本以上の異なるひもが結んでいることはありません。

すぬけ君は、2 人のおもちゃが同じ形であるかどうか気になっています。
ここで、2 人のおもちゃが同じ形であるとは、以下の条件を満たす数列 P が存在することをいいます。

  • P は (1, \dots, N) を並べ替えて得られる。
  • 任意の 1 以上 N 以下の整数 i, j に対し、以下が成り立つ。
    • 高橋君のおもちゃにおいてボール i, j がひもで繋がれていることと、青木君のおもちゃにおいてボール P_i, P_j がひもで繋がれていることは同値である。

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力してください。

制約

  • 1 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
  • (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
  • 入力は全て整数である。

入力

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

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

出力

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力せよ。


入力例 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

出力例 1

Yes

高橋君のおもちゃは下図の左側のような形をしており、青木君のおもちゃは下図の右側のような形をしています。

yes1

次の図から、2 人のおもちゃが同じ形であることがわかります。例えば P = (3, 2, 1, 4) とすると問題文中の条件を満たします。

yes2


入力例 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

出力例 2

No

2 人のおもちゃは同じ形ではありません。

no


入力例 3

8 0

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

  • P is a permutation of (1, \dots, N).
  • For every pair of integers i, j between 1 and N (inclusive), the following holds.
    • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

  • 1 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
  • (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

Output

If the two toys have the same shape, print Yes; otherwise, print No.


Sample Input 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

yes1

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

yes2


Sample Input 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

Sample Output 2

No

The two toys do not have the same shape.

no


Sample Input 3

8 0

Sample Output 3

Yes
F - Sum of Product

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

\displaystyle \sum_{1\leq i< j\leq N} A_iA_j の値を求めてください。

制約

  • 2\leq N \leq 3\times 10^5
  • 1\leq A_i \leq 10^4
  • 入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

3
4 2 3

出力例 1

26

\displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26 です。


入力例 2

2
9 45

出力例 2

405

入力例 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

出力例 3

3227530139

Score : 300 points

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \dots, A_N).

Compute the value of \displaystyle \sum_{1\leq i< j\leq N} A_iA_j.

Constraints

  • 2 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^4
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Output the answer.


Sample Input 1

3
4 2 3

Sample Output 1

26

We have \displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26.


Sample Input 2

2
9 45

Sample Output 2

405

Sample Input 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

Sample Output 3

3227530139
G - I Hate Non-integer Number

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

項数が N の正整数列 A=(a_1,\ldots,a_N) が与えられます。
A の項を 1 個以上選ぶ方法は 2^N-1 通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq a_i \leq 10^9
  • 入力はすべて整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。


入力例 1

3
2 6 2

出力例 1

6

A の項を選ぶ方法それぞれに対する平均値は以下のようになります。

  • a_1 のみを選んだ場合、平均値は \frac{a_1}{1}=\frac{2}{1} = 2 であり、整数である。

  • a_2 のみを選んだ場合、平均値は \frac{a_2}{1}=\frac{6}{1} = 6 であり、整数である。

  • a_3 のみを選んだ場合、平均値は \frac{a_3}{1}=\frac{2}{1} = 2 であり、整数である。

  • a_1 と a_2 を選んだ場合、平均値は \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4 であり、整数である。

  • a_1 と a_3 を選んだ場合、平均値は \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2 であり、整数である。

  • a_2 と a_3 を選んだ場合、平均値は \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4 であり、整数である。

  • a_1 と a_2 と a_3 を選んだ場合、平均値は \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3} であり、整数ではない。

以上より、6 通りの選び方が条件を満たします。


入力例 2

5
5 5 5 5 5

出力例 2

31

どのように A の項を 1 個以上選んでも平均値が 5 になります。

Score : 400 points

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq a_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.


Sample Input 1

3
2 6 2

Sample Output 1

6

For each way to choose terms of A, the average is obtained as follows:

  • If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.

  • If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.

  • If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.

  • If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.

  • If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.

  • If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.

  • If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.

Therefore, 6 ways satisfy the condition.


Sample Input 2

5
5 5 5 5 5

Sample Output 2

31

Regardless of the choice of one or more terms of A, the average equals 5.

H - Roulettes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 台のルーレットがあります。 i 番目 (1\leq i\leq N) のルーレットには P _ i 個の整数 S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} が書かれており、C _ i 円支払うことで 1 回プレイできます。 i 番目のルーレットを 1 回プレイすると、1 以上 P _ i 以下の整数 j が一様ランダムに選ばれ、S _ {i,j} ポイントを得ることができます。

ルーレットで得られるポイントは、過去の結果と独立に決まります。

高橋くんは、ポイントを M ポイント以上獲得したいです。 高橋くんは、M ポイント以上獲得するまでに支払う金額をなるべく小さくするように行動します。 ただし、高橋くんはルーレットをプレイするたびこれまでのルーレットの結果を見て次にプレイするルーレットを選ぶことができます。

高橋くんがポイントを M ポイント以上獲得するまでに支払う金額の期待値を求めてください。

より厳密な定義

より厳密には、次のようになります。 高橋くんがルーレットを選ぶ戦略を決めるごとに、その戦略で M ポイント以上獲得するまでに支払う金額の期待値 E が次のように定義されます。

  • 自然数 X に対して、その戦略に従って高橋くんが M ポイント以上獲得するか、ルーレットを X 回プレイするまでに支払う金額の期待値を f(X) とする。E=\displaystyle\lim _ {X\to+\infty}f(X) とする。

この問題の条件のもとで、高橋くんがどのような戦略をとっても \displaystyle\lim _ {X\to+\infty}f(X) が有限の値になることが証明できます。 高橋くんが E を最小にするような戦略をとったときの E の値を求めてください。

制約

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
  • 1\leq P _ i\leq 100\ (1\leq i\leq N)
  • 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
  • \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
  • 入力はすべて整数

入力

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

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

出力

高橋くんが M ポイント以上獲得するまでに支払う金額の期待値を 1 行で出力せよ。 出力された値と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき、正答と判定される。


入力例 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

出力例 1

215.913355350494384765625

例えば、高橋くんはルーレットを次のようにプレイすることができます。

  • 50 円を支払ってルーレット 2 をプレイする。S _ {2,4}=8 ポイントを得る。
  • 50 円を支払ってルーレット 2 をプレイする。S _ {2,1}=1 ポイントを得る。
  • 100 円を支払ってルーレット 1 をプレイする。S _ {1,1}=5 ポイントを得る。得たポイントの合計が 8+1+5\geq14 ポイントとなったため、終了する。

この例では、14 ポイントを得るまでに 200 円を支払っています。

出力と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき正答と判定されるため、215.9112 や 215.9155 などと出力しても正解になります。


入力例 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

出力例 2

60

100 ポイントが出るまでルーレット 2 を回し続けるのが最適です。


入力例 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

出力例 3

45037.072314895291126319493887599716

Score : 475 points

Problem Statement

There are N roulette wheels. The i-th (1\leq i\leq N) wheel has P _ i integers S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} written on it, and you can play it once by paying C _ i yen. When you play the i-th wheel once, an integer j between 1 and P _ i, inclusive, is chosen uniformly at random, and you earn S _ {i,j} points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least M points. Takahashi will act to minimize the amount of money he pays before he earns at least M points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least M points.

More formal definition

Here is a more formal statement. For a strategy that Takahashi can adopt in choosing which wheel to play, the expected amount of money E that he pays before he earns at least M points with that strategy is defined as follows.

  • For a natural number X, let f(X) be the expected amount of money Takahashi pays before he earns at least M points or plays the wheels X times in total according to that strategy. Let E=\displaystyle\lim _ {X\to+\infty}f(X).

Under the conditions of this problem, it can be proved that \displaystyle\lim _ {X\to+\infty}f(X) is finite no matter what strategy Takahashi adopts. Find the value of E when he adopts a strategy that minimizes E.

Constraints

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
  • 1\leq P _ i\leq 100\ (1\leq i\leq N)
  • 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
  • \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
  • All input values are integers.

Input

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

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

Output

Print the expected amount of money Takahashi will pay until he earns at least M points in a single line. Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}.


Sample Input 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

  • Pay 50 yen to play roulette 2 and earn S _ {2,4}=8 points.
  • Pay 50 yen to play roulette 2 and earn S _ {2,1}=1 point.
  • Pay 100 yen to play roulette 1 and earn S _ {1,1}=5 points. He has earned a total of 8+1+5\geq14 points, so he quits playing.

In this case, he pays 200 yen before earning 14 points.

Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}, so outputs such as 215.9112 and 215.9155 would also be considered correct.


Sample Input 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

Sample Output 2

60

It is optimal to keep spinning roulette 2 until you get 100 points.


Sample Input 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

Sample Output 3

45037.072314895291126319493887599716
I - Shortest One Formula

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

正整数 N が与えられます。

1, +, *, (, ) のみからなる数式のうち、値が N となるものの中で、文字列としての長さが最小のものを一つ求めてください。

より厳密には、以下の条件をすべて満たす文字列 S のうち長さが最小のものを一つ求めてください。

  • S は下の BNF 記法 の <expr> シンボルに従う文字列である。
  • S が表す数式の値は N である。
<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number> 

<expr> シンボルに従う文字列として、以下のようなものがあります。

  • 1111+111 : 1111+111 を表します。
  • (1+1)*(1+1) : (1+1)\times (1+1) を表します。
  • (11+(1+1)*(1+1))+1 : (11+(1+1)\times (1+1))+1 を表します。

一方、以下の文字列は <expr> シンボルに従いません。

  • (1+1)(1+1)
  • 1+2
  • 1-1
  • 1/1
  • )1(
  • 1++1
  • +1
  • (+1)
  • 1*+1

制約

  • 1\leq N\leq 2000
  • 入力は全て整数

入力

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

N

出力

答えを出力せよ。


入力例 1

9

出力例 1

(1+1+1)*(1+1+1)

値が 9 となるような数式は例えば以下のようなものがあります。

  • (1+1+1)*(1+1+1)
  • 1+1+1+1+1+1+1+1+1
  • (1+1)*(1+1)*(1+1)+1

値が 9 となるような数式のうち、長さが最小となるものは (1+1+1)*(1+1+1) です。


入力例 2

11

出力例 2

11

入力例 3

403

出力例 3

1+(1+1+1)*(1+11+11+111)

Score : 500 points

Problem Statement

You are given a positive integer N.

Among all valid arithmetic expressions consisting of the characters 1, +, *, (, and ), find one of the minimum length whose value is N.

More formally, among the strings S satisfying all of the following conditions, find one of the minimum length:

  • S conforms to the symbol <expr> in the BNF below.
  • The value of the expression represented by S is N.
<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>

Strings that conform to <expr> include:

  • 1111+111 representing 1111+111.
  • (1+1)*(1+1) representing (1+1)\times(1+1).
  • (11+(1+1)*(1+1))+1 representing (11+(1+1)\times(1+1))+1.

Strings that do not conform to <expr> include:

  • (1+1)(1+1)
  • 1+2
  • 1-1
  • 1/1
  • )1(
  • 1++1
  • +1
  • (+1)
  • 1*+1

Constraints

  • 1 \le N \le 2000
  • All input values are integers.

Input

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

N

Output

Print a solution.


Sample Input 1

9

Sample Output 1

(1+1+1)*(1+1+1)

Expressions whose value is 9 include:

  • (1+1+1)*(1+1+1)
  • 1+1+1+1+1+1+1+1+1
  • (1+1)*(1+1)*(1+1)+1

Among them, a shortest is (1+1+1)*(1+1+1).


Sample Input 2

11

Sample Output 2

11

Sample Input 3

403

Sample Output 3

1+(1+1+1)*(1+11+11+111)