A - 2UP3DOWN

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

高橋君が 100 階建てのビルにいます。

高橋君は 2 階分までの上り、または、3 階分までの下りであれば移動には階段を使い、そうでないときエレベーターを使います。

高橋君が X 階から Y 階への移動に使うのは階段ですか?

制約

  • 1 \leq X,Y \leq 100
  • X \neq Y
  • 入力は全ては整数である

入力

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

X Y

出力

移動に使うのが階段ならば Yes、エレベーターならば No を出力せよ。


入力例 1

1 4

出力例 1

No

1 階から 4 階への移動は 3 階分の上りなのでエレベーターを使います。


入力例 2

99 96

出力例 2

Yes

99 階から 96 階への移動は 3 階分の下りなので階段を使います。


入力例 3

100 1

出力例 3

No

Score : 100 points

Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

  • 1 \leq X,Y \leq 100
  • X \neq Y
  • All input values are integers.

Input

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

X Y

Output

If Takahashi uses the stairs for the move, print Yes; if he uses the elevator, print No.


Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.


Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.


Sample Input 3

100 1

Sample Output 3

No
B - 326-like Numbers

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。

例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。

整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。

制約

  • 100 \leq N \leq 919
  • N は整数である

入力

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

N

出力

答えを出力せよ。


入力例 1

320

出力例 1

326

320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。


入力例 2

144

出力例 2

144

144 は 326-like number です。


入力例 3

516

出力例 3

600

Score : 200 points

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

  • 100 \leq N \leq 919
  • N is an integer.

Input

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

N

Output

Print the answer.


Sample Input 1

320

Sample Output 1

326

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.


Sample Input 2

144

Sample Output 2

144

144 is a 326-like number.


Sample Input 3

516

Sample Output 3

600
C - Peak

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。

あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。

  • まず、実数 x をひとつ選択する。
  • その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。

最大でいくつのプレゼントを獲得することができますか?

制約

  • 入力は全て整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • 0 \le A_i \le 10^9

入力

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

N M
A_1 A_2 \dots A_N

出力

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


入力例 1

8 6
2 3 5 7 11 13 17 19

出力例 1

4

例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。


入力例 2

10 1
3 1 4 1 5 9 2 6 5 3

出力例 2

2

同一の座標に複数のプレゼントが置いてあることもあります。


入力例 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

出力例 3

7

Score : 300 points

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

  • First, choose one real number x.
  • Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

  • All input values are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • 0 \le A_i \le 10^9

Input

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

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.


Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.


Sample Input 2

10 1
3 1 4 1 5 9 2 6 5 3

Sample Output 2

2

There may be multiple gifts at the same coordinate.


Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7
D - ABC Puzzle

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 450

問題文

整数 NA, B, C からなる長さ N の文字列 R,C が与えられるので、以下の問題を解いてください。

N \times N のマス目があり、最初全てのマスは空きマスです。
各マスに A, B, C のうち高々 1 文字を書き込みます。( 空きマスのままにすることも許されます )

以下の条件を全て満たすことが可能であるか判定し、可能であれば書き込み方を 1 つ出力して下さい。

  • 各行 / 各列 に A, B, C がちょうど 1 個ずつ含まれる
  • i 行目に書かれた文字の中で最も左にある文字は Ri 文字目と一致する
  • i 列目に書かれた文字の中で最も上にある文字は Ci 文字目と一致する

制約

  • N3 以上 5 以下の整数
  • R,CA, B, C からなる長さ N の文字列

入力

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

N
R
C

出力

問題文中の条件を満たす書き込み方が存在しない場合、 No1 行に出力してください。
そうでない場合、以下の形式に従い書き込み方を出力してください。

Yes
A_1
A_2
\vdots
A_N

まず、 1 行目に Yes と出力してください。 続く N 行のうちの i 行目に、長さ N の文字列である A_i を出力してください。

  • A_ij 文字目が . であるとき、上から i 行目、左から j 列目のマスは空きマスであることを示します。
  • A_ij 文字目が A であるとき、上から i 行目、左から j 列目のマスに A が書き込まれたことを示します。
  • A_ij 文字目が B であるとき、上から i 行目、左から j 列目のマスに B が書き込まれたことを示します。
  • A_ij 文字目が C であるとき、上から i 行目、左から j 列目のマスに C が書き込まれたことを示します。

正しい書き込み方が複数存在する場合、どれを出力しても構いません。


入力例 1

5
ABCBC
ACAAB

出力例 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

出力例のマス目は以下の条件を全て満たすため、正解として扱われます。

  • 全ての行に A, B, C がちょうど 1 個ずつ含まれる
  • 全ての列に A, B, C がちょうど 1 個ずつ含まれる
  • 各行に書かれた最も左の文字は上から順に A, B, C, B, C である
  • 各列に書かれた最も上の文字は左から順に A, C, A, A, B である

入力例 2

3
AAA
BBB

出力例 2

No

この入力では、条件を満たす書き込み方は存在しません。

Score : 450 points

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

  • Each row and each column contain exactly one A, one B, and one C.
  • The leftmost character written in the i-th row matches the i-th character of R.
  • The topmost character written in the i-th column matches the i-th character of C.

Constraints

  • N is an integer between 3 and 5, inclusive.
  • R and C are strings of length N consisting of A, B, and C.

Input

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

N
R
C

Output

If there is no way to fill the grid to satisfy the conditions in the problem statement, print No in one line.
Otherwise, print one such way to fill the grid in the following format:

Yes
A_1
A_2
\vdots
A_N

The first line should contain Yes. The i-th of the subsequent N lines should contain a string A_i of length N.

  • If the j-th character of A_i is ., it indicates that the cell in the i-th row from the top and the j-th column from the left is empty.
  • If the j-th character of A_i is A, it indicates that A is written in the cell in the i-th row from the top and the j-th column from the left.
  • If the j-th character of A_i is B, it indicates that B is written in the cell in the i-th row from the top and the j-th column from the left.
  • If the j-th character of A_i is C, it indicates that C is written in the cell in the i-th row from the top and the j-th column from the left.

If there are multiple correct ways to fill the grid, you may print any of them.


Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

  • Each row contains exactly one A, one B, and one C.
  • Each column contains exactly one A, one B, and one C.
  • The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
  • The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.

E - Revenge of "The Salary of AtCoder Inc."

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450

問題文

AtCoder社の社員である青木さんの今月の給料は、整数 N と長さ N の数列 A を用いて以下のように決められます。
まず、青木さんに 1 から N までの整数が等確率で出る N 面ダイスと変数 x=0 を渡します。

その後、以下の手順を終了まで繰り返します。

  • ダイスを 1 度振り、出た目を y とする。
    • もし x<y なら A_y 円支給し、 x=y と更新する。
    • そうでないなら終了する。

青木さんの今月の給料は、この手順によって支給された金額の合計です。
青木さんの今月の給料の期待値を {}\bmod{998244353} で求めてください。

期待値 {}\bmod{998244353} の定義 この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac yx で表したときに x998244353 で割り切れないことが保証されます。 このとき、y\equiv xz\pmod{998244353} を満たす 0\leq z\lt998244353 がただ一つ存在するので、z を出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 3 \times 10^5
  • 0 \le A_i < 998244353

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

3
3 2 6

出力例 1

776412280

手順の一例は、以下の通りです。

  • 最初、 x=0 である。
  • ダイスを 1 度振り、出た目が 1 であった。 0<1 であるため、 A_1 = 3 円支給し、 x=1 とする。
  • ダイスを 1 度振り、出た目が 3 であった。 1<3 であるため、 A_3 = 6 円支給し、 x=3 とする。
  • ダイスを 1 度振り、出た目が 1 であった。 3 \ge 1 であるため、終了する。

この例では、青木さんの今月の給料は 9 円です。

なお、青木さんの今月の給料の期待値は \frac{49}{9} 円と求めることができ、これを {}\bmod{998244353} 上で表現すると 776412280 となります。


入力例 2

1
998244352

出力例 2

998244352

入力例 3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

出力例 3

545252774

Score : 450 points

Problem Statement

Aoki, an employee at AtCoder Inc., has his salary for this month determined by an integer N and a sequence A of length N as follows.
First, he is given an N-sided die (dice) that shows the integers from 1 to N with equal probability, and a variable x=0.

Then, the following steps are repeated until terminated.

  • Roll the die once and let y be the result.
    • If x<y, pay him A_y yen and let x=y.
    • Otherwise, terminate the process.

Aoki's salary for this month is the total amount paid through this process.
Find the expected value of Aoki's salary this month, modulo 998244353.

How to find an expected value modulo 998244353 It can be proved that the sought expected value in this problem is always a rational number. Also, the constraints of this problem guarantee that if the sought expected value is expressed as a reduced fraction \frac yx, then x is not divisible by 998244353. Here, there is exactly one 0\leq z\lt998244353 such that y\equiv xz\pmod{998244353}. Print this z.

Constraints

  • All inputs are integers.
  • 1 \le N \le 3 \times 10^5
  • 0 \le A_i < 998244353

Input

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

N
A_1 A_2 \dots A_N

Output

Print the answer.


Sample Input 1

3
3 2 6

Sample Output 1

776412280

Here is an example of how the process goes.

  • Initially, x=0.
  • Roll the die once, and it shows 1. Since 0<1, pay him A_1 = 3 yen and let x=1.
  • Roll the die once, and it shows 3. Since 1<3, pay him A_3 = 6 yen and let x=3.
  • Roll the die once, and it shows 1. Since 3 \ge 1, terminate the process.

In this case, his salary for this month is 9 yen.

It can be calculated that the expected value of his salary this month is \frac{49}{9} yen, whose representation modulo 998244353 is 776412280.


Sample Input 2

1
998244352

Sample Output 2

998244352

Sample Input 3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

Sample Output 3

545252774
F - Robot Rotation

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 525

問題文

右向きを x 軸正方向、上向きを y 軸正方向とする座標平面の原点にロボットがいます。ロボットは最初、x 軸正方向を向いています。

i=1,\ldots,N の順に以下の操作を行います:

  • ロボットを右回りまたは左回りに 90 度回転させる。その後、ロボットは向いている方向に A_i 進む

回転方向を適切に選ぶことで、N 回の操作後にロボットがいる座標を (X,Y) にすることはできますか?

できるならば、各操作において、右回りと左回りのどちらを選べばよいか求めてください。

制約

  • 1 \leq N \leq 80
  • 1 \leq A_i \leq 10^7
  • -10^9\leq X,Y \leq 10^9
  • 入力は全て整数である

入力

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

N X Y
A_1 \ldots A_N

出力

N 回の操作後にロボットがいる座標を (X,Y) にできないとき、No と出力せよ。
N 回の操作後にロボットがいる座標を (X,Y) にできるとき、1行目に Yes と出力し、2行目に次の条件を満たす長さ N の文字列 S を出力せよ。
条件: SL または R のみからなり、Si 番目の文字が L ならば i 回目の操作においてロボットを左回りに、R ならばロボットを右回りに回転させることで、N 回の操作後にロボットがいる座標を (X,Y) にできる。

答えが複数ある場合はどれを出力しても正解となる。


入力例 1

3 -2 4
3 2 1

出力例 1

Yes
LLR

最初ロボットは (0,0) にいて、x 軸正方向を向いています。次の手順により、N 回の操作後にロボットがいる座標を (X,Y) にできます。

  • 1 回目の操作:ロボットを左に 90 度回転させ、y 軸正方向を向かせる。ロボットは向いている方向に A_1=3 進み、ロボットのいる座標は (0,3) となる。
  • 2 回目の操作:ロボットを左に 90 度回転させ、x 軸負方向を向かせる。ロボットは向いている方向に A_2=2 進み、ロボットのいる座標は (-2,3) となる。
  • 3 回目の操作:ロボットを右に 90 度回転させ、y 軸正方向を向かせる。ロボットは向いている方向に A_3=1 進み、ロボットのいる座標は (-2,4) となる。

図


入力例 2

1 0 0
1

出力例 2

No

入力例 3

4 0 0
1 1 1 1

出力例 3

Yes
LRRR

LLLLRRRR などでも正解となります。


入力例 4

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

出力例 4

Yes
LLLLLLLLLRLRRR

Score : 525 points

Problem Statement

A robot is at the origin of a coordinate plane where the positive x-axis points to the right and the positive y-axis points upwards. Initially, the robot is facing the positive x-direction.

You will perform the following operation for i=1,\ldots,N in this order.

  • Rotate the robot 90 degrees clockwise or counterclockwise. Then, the robot moves forward A_i units in the direction it is facing.

Can the direction of rotation be chosen so that the robot will be at the coordinates (X,Y) after the N operations?

If it is possible, determine which direction, clockwise or counterclockwise, should be chosen for each operation.

Constraints

  • 1 \leq N \leq 80
  • 1 \leq A_i \leq 10^7
  • -10^9\leq X,Y \leq 10^9
  • All input values are integers.

Input

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

N X Y
A_1 \ldots A_N

Output

If the robot cannot be at the coordinates (X,Y) after the N operations, print No.
If the robot can be at the coordinates (X,Y) after the N operations, the first line should contain Yes, and the second line should contain a string S of length N that satisfies the following condition.
Condition: S consists of L and R, and the following choices can put the robot at the coordinates (X,Y) after the N operations: in the i-th operation, rotate the robot counterclockwise if the i-th character of S is L, and rotate it clockwise if it is R.

If there are multiple solutions, you may print any of them.


Sample Input 1

3 -2 4
3 2 1

Sample Output 1

Yes
LLR

Initially, the robot is at (0,0) and facing the positive x-direction. The following choices can put the robot at the coordinates (X,Y) after the N operations.

  • First operation: Rotate the robot 90 degrees counterclockwise to face the positive y-direction. The robot moves forward A_1=3 units in the direction it is facing, and moves to (0,3).
  • Second operation: Rotate the robot 90 degrees counterclockwise to face the negative x-direction. The robot moves forward A_2=2 units in the direction it is facing, and moves to (-2,3).
  • Third operation: Rotate the robot 90 degrees clockwise to face the positive y-direction. The robot moves forward A_3=1 unit in the direction it is facing, and moves to (-2,4).

Diagram


Sample Input 2

1 0 0
1

Sample Output 2

No

Sample Input 3

4 0 0
1 1 1 1

Sample Output 3

Yes
LRRR

Outputs such as LLLL and RRRR are also accepted.


Sample Input 4

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

Sample Output 4

Yes
LLLLLLLLLRLRRR
G - Unlock Achievement

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 625

問題文

1 から N の番号がついた N 種類のスキルと、1 から M の番号がついた M 種類のアチーブメントがあります。

各スキルには正整数のレベルが定まっており、最初全てのスキルのレベルは 1 です。

C_i 円のコストを払うことでスキル i のレベルを 1 上げることができます。これは何度でも行なえます。

アチーブメント i は、j=1,\ldots,N の全てについて以下の条件を満たすと達成となり、A_i 円の報酬をもらえます。

  • 条件:スキル j のレベルが L_{i,j} 以上である

スキルのレベルの上げ方を適切に選ぶとき、得られる報酬の合計から必要なコストの合計を引いた値の最大値を求めてください。

制約

  • 1 \leq N,M \leq 50
  • 1 \leq L_{i,j} \leq 5
  • 1 \leq A_i,C_i \leq 10^6
  • 入力は全て整数である

入力

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

N M
C_1 \ldots C_N
A_1 \ldots A_M
L_{1,1} \ldots L_{1,N}
\vdots
L_{M,1} \ldots L_{M,N}

出力

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


入力例 1

2 2
10 20
100 50
3 1
1 4

出力例 1

80

2 種類のスキルがあります。スキル 1 はレベルを上げるために 10 円、スキル 220 円かかります。
2 種類のアチーブメントがあります。 アチーブメント 1 は「スキル 1 をレベル 3 以上、かつ、スキル 2 をレベル 1 以上」にすると達成となり 100 円もらえ、 アチーブメント 2 は「スキル 1 をレベル 1 以上、かつ、スキル 2 をレベル 4 以上」にすると達成となり 50 円もらえます。

スキル 1 をレベル 3 に、スキル 2 をレベル 1 にすることで、報酬が 100 円、コストが 20 円となり、その差は 80 円となります。


入力例 2

2 2
10 20
100 50
3 2
1 4

出力例 2

70

スキル 1 をレベル 3 に、スキル 2 をレベル 4 にすることで、報酬が 150 円、コストが 80 円となり、その差は 70 円となります。


入力例 3

10 10
10922 23173 32300 22555 29525 16786 3135 17046 11245 20310
177874 168698 202247 31339 10336 14825 56835 6497 12440 110702
2 1 4 1 3 4 4 5 1 4
2 3 4 4 5 3 5 5 2 3
2 3 5 1 4 2 2 2 2 5
3 5 5 3 5 2 2 1 5 4
3 1 1 4 4 1 1 5 3 1
1 2 3 2 4 2 4 3 3 1
4 4 4 2 5 1 4 2 2 2
5 3 1 2 3 4 2 5 2 2
5 4 3 4 3 1 5 1 5 4
2 3 2 5 2 3 1 2 2 4

出力例 3

66900

Score : 625 points

Problem Statement

There are N skills numbered 1 to N and M achievements numbered 1 to M.

Each skill has a positive integer level, and the initial level of every skill is 1.

You can pay a cost of C_i yen to increase the level of skill i by 1. You can do this as many times as you want.

Achievement i is achieved when the following condition is satisfied for every j=1,\ldots,N, for which you will receive a reward of A_i yen.

  • Condition: The level of skill j is at least L_{i,j}.

Find the maximum possible total reward obtained minus the total cost required when appropriately choosing how to raise the skill levels.

Constraints

  • 1 \leq N,M \leq 50
  • 1 \leq L_{i,j} \leq 5
  • 1 \leq A_i,C_i \leq 10^6
  • All input values are integers.

Input

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

N M
C_1 \ldots C_N
A_1 \ldots A_M
L_{1,1} \ldots L_{1,N}
\vdots
L_{M,1} \ldots L_{M,N}

Output

Print the answer as an integer.


Sample Input 1

2 2
10 20
100 50
3 1
1 4

Sample Output 1

80

There are two skills. It costs 10 yen to raise the level of skill 1 and 20 yen to raise the level of skill 2.
There are two achievements. Achievement 1 is achieved when skill 1 is at least level 3 and skill 2 is at least level 1, for which you will receive 100 yen. Achievement 2 is achieved when skill 1 is at least 1 and skill 2 is at least level 4, for which you will receive 50 yen.

By raising skill 1 to level 3 and skill 2 to level 1, you will receive the reward of 100 yen for the cost of 20 yen, and the balance is 80 yen.


Sample Input 2

2 2
10 20
100 50
3 2
1 4

Sample Output 2

70

By raising skill 1 to level 3 and skill 2 to level 4, you will receive the reward of 150 yen for the cost of 80 yen, and the balance is 70 yen.


Sample Input 3

10 10
10922 23173 32300 22555 29525 16786 3135 17046 11245 20310
177874 168698 202247 31339 10336 14825 56835 6497 12440 110702
2 1 4 1 3 4 4 5 1 4
2 3 4 4 5 3 5 5 2 3
2 3 5 1 4 2 2 2 2 5
3 5 5 3 5 2 2 1 5 4
3 1 1 4 4 1 1 5 3 1
1 2 3 2 4 2 4 3 3 1
4 4 4 2 5 1 4 2 2 2
5 3 1 2 3 4 2 5 2 2
5 4 3 4 3 1 5 1 5 4
2 3 2 5 2 3 1 2 2 4

Sample Output 3

66900