A - N-choice question

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 A,B が与えられるので、 A+B の値を答えてください。
但し、この問題は N 択問題であり、 i 番の選択肢は C_i です。
正解となる 選択肢の番号 を出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 300
  • 1 \le A,B \le 1000
  • 1 \le C_i \le 2000
  • C_i は相異なる。すなわち、同じ選択肢が複数存在することはない。
  • A+B=C_i なる i が丁度 1 つ存在する。すなわち、正解となる選択肢が必ずただ 1 つ存在する。

入力

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

N A B
C_1 C_2 \dots C_N

出力

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


入力例 1

3 125 175
200 300 400

出力例 1

2

125+175 = 300 です。
1 番の選択肢は 200 、 2 番の選択肢は 300 、 3 番の選択肢は 400 です。
よって正解となる選択肢の番号は 2 番であり、これを出力します。


入力例 2

1 1 1
2

出力例 2

1

1 択問題である場合もあります。


入力例 3

5 123 456
135 246 357 468 579

出力例 3

5

Score : 100 points

Problem Statement

Given integers A and B, find A+B.
This is a N-choice problem; the i-th choice is C_i.
Print the index of the correct choice.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 300
  • 1 \le A,B \le 1000
  • 1 \le C_i \le 2000
  • C_i are pairwise distinct. In other words, no two choices have the same value.
  • There is exactly one i such that A+B=C_i. In other words, there is always a unique correct choice.

Input

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

N A B
C_1 C_2 \dots C_N

Output

Print the answer as an integer.


Sample Input 1

3 125 175
200 300 400

Sample Output 1

2

We have 125+175 = 300.
The first, second, and third choices are 200, 300, and 400, respectively.
Thus, the 2-nd choice is correct, so 2 should be printed.


Sample Input 2

1 1 1
2

Sample Output 2

1

The problem may be a one-choice problem.


Sample Input 3

5 123 456
135 246 357 468 579

Sample Output 3

5
B - AtCoder Quiz 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 王国では、競技プログラミングの実力を測る検定試験が実施されています。

試験は 100 点満点であり、点数が高ければ高いほど、高いランクが認定されます。
ランクは以下のように定められています。

  • 0 点以上 40 点未満のとき、初級
  • 40 点以上 70 点未満のとき、中級
  • 70 点以上 90 点未満のとき、上級
  • 90 点以上のとき、エキスパート

高橋君は、この検定試験を受験し、X 点を取りました。

高橋君が認定されたランクより一つ高いランクとなるためには最低であと何点必要か求めてください。ただし、高橋君がエキスパートと認定された場合、それより高いランクは存在しないため expert と出力してください。

制約

  • 0 \leq X \leq 100
  • X は整数

入力

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

X

出力

答えを出力せよ。


入力例 1

56

出力例 1

14

高橋君は 56 点を取り、中級と認定されました。一つ高いランクである上級となるためには、最低であと 14 点必要です。


入力例 2

32

出力例 2

8

入力例 3

0

出力例 3

40

入力例 4

100

出力例 4

expert

高橋君は満点を取り、エキスパートと認定されました。これより高いランクは存在しないため、expert と出力します。

Score : 100 points

Problem Statement

In the Kingdom of AtCoder, there is a standardized test of competitive programming proficiency.

An examinee will get a score out of 100 and obtain a rank according to the score, as follows:

  • Novice, for a score not less than 0 but less than 40;
  • Intermediate, for a score not less than 40 but less than 70;
  • Advanced, for a score not less than 70 but less than 90;
  • Expert, for a score not less than 90.

Takahashi took this test and got X points.

Find the minimum number of extra points needed to go up one rank higher. If, however, his rank was Expert, print expert, as there is no higher rank than that.

Constraints

  • 0 \leq X \leq 100
  • X is an integer.

Input

Input is given from Standard Input in the following format:

X

Output

Print the answer.


Sample Input 1

56

Sample Output 1

14

He got 56 points and was certified as Intermediate. In order to reach the next rank of Advanced, he needs at least 14 more points.


Sample Input 2

32

Sample Output 2

8

Sample Input 3

0

Sample Output 3

40

Sample Input 4

100

Sample Output 4

expert

He got full points and was certified as Expert. There is no rank higher than that, so print expert.

C - Triangle (Easier)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, \dots, N の番号が付けられており、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

以下の条件を全て満たす整数 a, b, c の組の総数を求めてください。

  • 1 \leq a \lt b \lt c \leq N
  • 頂点 a と頂点 b を結ぶ辺が存在する。
  • 頂点 b と頂点 c を結ぶ辺が存在する。
  • 頂点 c と頂点 a を結ぶ辺が存在する。

制約

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • 入力は全て整数

入力

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

N M
U_1 V_1
\vdots
U_M V_M

出力

答えを出力せよ。


入力例 1

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

出力例 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) が条件を満たします。


入力例 2

3 1
1 2

出力例 2

0

入力例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

出力例 3

4

Score : 200 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

  • 1 \leq a \lt b \lt c \leq N
  • There is an edge connecting Vertex a and Vertex b.
  • There is an edge connecting Vertex b and Vertex c.
  • There is an edge connecting Vertex c and Vertex a.

Constraints

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
\vdots
U_M V_M

Output

Print the answer.


Sample Input 1

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

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.


Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

Sample Output 3

4
D - Prefix and Suffix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)

S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。

S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。

制約

  • 1 \leq N \leq M \leq 100
  • S は英小文字からなる長さ N の文字列
  • T は英小文字からなる長さ M の文字列

入力

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

N M
S
T

出力

問題文の指示に従って答えを出力せよ。


入力例 1

3 7
abc
abcdefg

出力例 1

1

S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。


入力例 2

3 4
abc
aabc

出力例 2

2

S は T の接尾辞ですが接頭辞ではありません。


入力例 3

3 3
abc
xyz

出力例 3

3

S は T の接頭辞でも接尾辞でもありません。


入力例 4

3 3
aaa
aaa

出力例 4

0

S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

  • 1 \leq N \leq M \leq 100
  • S is a string of length N consisting of lowercase English letters.
  • T is a string of length M consisting of lowercase English letters.

Input

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

N M
S
T

Output

Print the answer according to the instructions in the problem statement.


Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.


Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.


Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.


Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

E - Various Kagamimochi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。

2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。

N 個の餅から 2 つの餅を選び、一方をもう一方の上に乗せることで鏡餅を 1 つ作ります。

何種類の鏡餅を作ることができるか求めてください。

ただし、鏡餅を構成する餅の大きさが同じでも、少なくとも一方が異なる餅であれば別の種類の鏡餅として数えます。

制約

  • 2\leq N\leq 5\times 10 ^ 5
  • 1\leq A _ i\leq 10 ^ 9\ (1\leq i\leq N)
  • A _ i\leq A _ {i+1}\ (1\leq i\lt N)
  • 入力はすべて整数

入力

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

N
A _ 1 A _ 2 \cdots A _ N

出力

作ることができる鏡餅の種類数を出力せよ。


入力例 1

6
2 3 4 4 7 10

出力例 1

8

与えられた餅の大きさは以下のようになっています。

このとき、以下の 8 種類の鏡餅を作ることができます。

大きさ 4 の餅の上に大きさ 2 の餅を乗せた鏡餅や、大きさ 10 の餅の上に大きさ 4 の餅を乗せた鏡餅は 2 種類あることに注意してください。


入力例 2

3
387 388 389

出力例 2

0

鏡餅を 1 種類も作ることができない場合もあります。


入力例 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

出力例 3

388

Score : 300 points

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • A_i \leq A_{i+1} \ (1 \leq i < N)
  • All input values are integers.

Input

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

N
A_1 A_2 \cdots A_N

Output

Print the number of different kinds of kagamimochi that can be made.


Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.


Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.


Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388
F - Truck Driver

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 国には「トラック運転手は A 分以上運転する際には B 分以上の休憩を取らなければならない」というルールがあります。

a, b からなる長さ N の文字列 S と正整数 A,B が与えられます。以下の条件を全て満たす整数組 (l,r) の個数を求めてください。

  • 1\leq l \leq r \leq N
  • S の l 文字目から r 文字目までに含まれる a の個数が A 以上
  • S の l 文字目から r 文字目までに含まれる b の個数が B 未満

制約

  • 1\leq N \leq 3\times 10^5
  • 1 \leq A,B \leq N
  • S は a, b のみからなる長さ N の文字列
  • 与えられる数値は全て整数

入力

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

N A B
S

出力

答えを出力せよ。


入力例 1

11 4 2
abbaaabaaba

出力例 1

3

条件を満たす (l,r) の組は (4,8),(4,9),(5,9) の 3 個です。


入力例 2

13 1 2
bbbbbbbbbbbbb

出力例 2

0

条件を満たす (l,r) の組は存在しません。

Score : 300 points

Problem Statement

In AtCoder Country, there is a rule that "a truck driver must take a break of at least B minutes when driving for A minutes or more."

You are given a string S of length N consisting of a and b, and positive integers A and B. Find the number of integer pairs (l,r) that satisfy all of the following conditions.

  • 1\leq l \leq r \leq N
  • The number of a in the substring from the l-th character through the r-th character of S is greater than or equal to A.
  • The number of b in the substring from the l-th character through the r-th character of S is less than B.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 1 \leq A,B \leq N
  • S is a string of length N consisting of a and b.
  • All input numbers are integers.

Input

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

N A B
S

Output

Print the answer.


Sample Input 1

11 4 2
abbaaabaaba

Sample Output 1

3

The pairs (l,r) that satisfy the conditions are (4,8),(4,9),(5,9), which is three pairs.


Sample Input 2

13 1 2
bbbbbbbbbbbbb

Sample Output 2

0

There are no pairs (l,r) that satisfy the conditions.

G - Pyramid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

正の整数 k について、サイズ k の ピラミッド数列 とは、長さ (2k-1) の数列であって各項の値が順に 1,2,\ldots,k-1,k,k-1,\ldots,2,1 であるようなものをさします。

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に対して、次の操作のうち一方を選んで行うことを繰り返して (0 回でも良い) 得ることのできるピラミッド数列のサイズの最大値を求めてください。

  • 数列の項を 1 つ選び、その項の値を 1 減少させる。
  • 先頭または末尾の項を削除する。

なお、問題の制約のもとで、操作を繰り返すことで必ず 1 種類以上のピラミッド数列を得ることができることが証明できます。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq 10^9
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

数列 A に問題文の操作を繰り返して得ることのできるピラミッド数列のサイズの最大値を出力せよ。


入力例 1

5
2 2 3 1 1

出力例 1

2

A=(2,2,3,1,1) から始めて、 次のようにして数列 A からサイズ 2 のピラミッド数列を作る事ができます。

  • 第 3 項を選び、1 減少させる。数列は A=(2,2,2,1,1) となる。
  • 先頭を削除する。数列は A=(2,2,1,1) となる。
  • 末尾を削除する。数列は A=(2,2,1) となる。
  • 第 1 項を選び、1 減少させる。数列は A=(1,2,1) となる。

(1,2,1) はサイズ 2 のピラミッド数列です。
一方、どのように操作を行ってもサイズ 3 以上のピラミッド数列を作ることはできないため 2 を出力します。


入力例 2

5
1 2 3 4 5

出力例 2

3

入力例 3

1
1000000000

出力例 3

1

Score: 400 points

Problem Statement

For a positive integer k, the Pyramid Sequence of size k is a sequence of length (2k-1) where the terms of the sequence have the values 1,2,\ldots,k-1,k,k-1,\ldots,2,1 in this order.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
Find the maximum size of a Pyramid Sequence that can be obtained by repeatedly choosing and performing one of the following operations on A (possibly zero times).

  • Choose one term of the sequence and decrease its value by 1.
  • Remove the first or last term.

It can be proved that the constraints of the problem guarantee that at least one Pyramid Sequence can be obtained by repeating the operations.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq 10^9
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the maximum size of the Pyramid Sequence that can be obtained by repeatedly performing the operations described in the problem statement on the sequence A.


Sample Input 1

5
2 2 3 1 1

Sample Output 1

2

Starting with A=(2,2,3,1,1), you can create a Pyramid Sequence of size 2 as follows:

  • Choose the third term and decrease it by 1. The sequence becomes A=(2,2,2,1,1).
  • Remove the first term. The sequence becomes A=(2,2,1,1).
  • Remove the last term. The sequence becomes A=(2,2,1).
  • Choose the first term and decrease it by 1. The sequence becomes A=(1,2,1).

(1,2,1) is a Pyramid Sequence of size 2.
On the other hand, there is no way to perform the operations to create a Pyramid Sequence of size 3 or larger, so you should print 2.


Sample Input 2

5
1 2 3 4 5

Sample Output 2

3

Sample Input 3

1
1000000000

Sample Output 3

1
H - Unbalanced ABC Substrings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

A, B, C の 3 種類の文字のみからなる長さ N の文字列 S が与えられます。
S の空でない部分文字列は \frac{N(N+1)}{2} 個ありますが、そのうち以下の条件を満たすものがいくつあるか求めてください。

  • A, B, C の出現回数が相異なる。

ただし、2 つの部分文字列は、S から取り出す場所が異なれば文字列として同じでも区別して数えることに注意してください。

部分文字列とは? S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、AB は ABC の部分文字列ですが、AC は ABC の部分文字列ではありません。

制約

  • 1 \leq N \leq 2 \times 10^5
  • |S|=N
  • N は整数
  • S は A, B, C の 3 種類の文字のみからなる文字列

入力

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

N
S

出力

答えを 1 行で出力せよ。


入力例 1

6
AABBCC

出力例 1

4

S の先頭から 0 文字、末尾から 3 文字を削除すると AAB となり、これは条件を満たします。
S の先頭から 1 文字、末尾から 2 文字を削除すると ABB となり、これは条件を満たします。
S の先頭から 2 文字、末尾から 1 文字を削除すると BBC となり、これは条件を満たします。
S の先頭から 3 文字、末尾から 0 文字を削除すると BCC となり、これは条件を満たします。
また、これら以外の部分文字列は条件を満たしません。


入力例 2

6
ABCABC

出力例 2

0

どの部分文字列も条件を満たしません。


入力例 3

10
ACABCAABAB

出力例 3

17

Score : 450 points

Problem Statement

You are given a string S of length N consisting of the three characters A, B, and C.
There are \frac{N(N+1)}{2} non-empty substrings of S; find how many of them satisfy the following condition:

  • The numbers of occurrences of A, B, and C are all distinct from each other.

Count two substrings separately if they are taken from different positions in S, even if they are identical as strings.

What is a substring? A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, AB is a substring of ABC, but AC is not a substring of ABC.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • |S|=N
  • N is an integer.
  • S is a string consisting of the three characters A, B, and C.

Input

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

N
S

Output

Output the answer on a single line.


Sample Input 1

6
AABBCC

Sample Output 1

4

Deleting 0 characters from the beginning and 3 characters from the end of S gives AAB, which satisfies the condition.
Deleting 1 character from the beginning and 2 characters from the end of S gives ABB, which satisfies the condition.
Deleting 2 characters from the beginning and 1 character from the end of S gives BBC, which satisfies the condition.
Deleting 3 characters from the beginning and 0 characters from the end of S gives BCC, which satisfies the condition.
No other substrings satisfy the condition.


Sample Input 2

6
ABCABC

Sample Output 2

0

No substring satisfies the condition.


Sample Input 3

10
ACABCAABAB

Sample Output 3

17
I - Sensor Optimization Dilemma

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

キーエンスの工場長であるあなたは、ベルトコンベア上のいくつかの区間をセンサーによって監視したいと考えています。 あなたが監視したい区間は全部で N 個あり、i 個目の区間の長さは D_i メートルです。

センサーには 2 種類の候補があり、それぞれのセンサーに関する情報は以下の通りです。

  • センサー j\ (1\leq j \leq 2) : 長さ L_j メートルの区間を監視できる。 価格は 1 個あたり C_j であり、全体で最大 K_j 個まで使用することができる。

1 つの区間をいくつかの区間に分割して監視することもできます。 また、センサーが監視する区間が重なっていたり、監視したい区間の長さより余分に監視していたりしても問題はありません。 例えば、L_1=4,L_2=2 であるとき、センサー 1 を 1 つ使って長さ 3 メートルの区間を監視したり、センサー 1,2 を 1 つずつ使って長さ 5 メートルの区間を監視したりすることが可能です。

N 個の区画をすべて監視することが可能であるか判定し、可能ならば必要なセンサーの価格の総和の最小値を求めてください。

制約

  • 1\leq N \leq 100
  • 1\leq D_i,L_j \leq 10^5
  • 1\leq C_j \leq 10^9
  • 1\leq K_j \leq 10^3
  • 入力は全て整数

入力

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

N
D_1 D_2 \dots D_N
L_1 C_1 K_1
L_2 C_2 K_2

出力

N 個の区画をすべて監視することが不可能ならば -1 を、可能ならば必要なセンサーの価格の総和の最小値を出力せよ。


入力例 1

3
3 5 10
4 3 3
2 2 6

出力例 1

17

以下のようにすることで、センサー 1 を 3 つ、センサー 2 を 4 つ使ってすべての区間を監視できます。

  • センサー 1 を 1 つ使って 1 個目の区間を監視する。
  • センサー 1,2 を 1 つずつ使って 2 個目の区間を監視する。
  • センサー 1 を 1 つ、センサー 2 を 3 つ使って 3 個目の区間を監視する。

このとき、必要なセンサーの価格の総和は 3\times 3 + 2\times 4 = 17 であり、これが最小です。


入力例 2

3
3 5 10
4 3 3
2 2 3

出力例 2

-1

入力例 3

2
4 8
3 1 100
4 10000 100

出力例 3

5

1 つも使わない種類のセンサーがあっても構いません。

Score : 500 points

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of N sections you want to monitor, and the length of the i-th section is D_i meters.

There are two types of sensors to choose from, and below is some information about each sensor.

  • Type-j sensor (1\leq j \leq 2): Can monitor a section of length L_j meters. The price is C_j per sensor, and you can use at most K_j sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when L_1=4 and L_2=2, you can use one type-1 sensor to monitor a section of length 3 meters, or use one type-1 and one type-2 sensor to monitor a section of length 5 meters.

Determine whether it is possible to monitor all N sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

  • 1\leq N \leq 100
  • 1\leq D_i,L_j \leq 10^5
  • 1\leq C_j \leq 10^9
  • 1\leq K_j \leq 10^3
  • All input values are integers.

Input

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

N
D_1 D_2 \dots D_N
L_1 C_1 K_1
L_2 C_2 K_2

Output

If it is impossible to monitor all N sections, print -1. Otherwise, print the minimum total cost of the necessary sensors.


Sample Input 1

3
3 5 10
4 3 3
2 2 6

Sample Output 1

17

You can monitor all sections by using three type-1 sensors and four type-2 sensors as follows.

  • Use one type-1 sensor to monitor the first section.
  • Use one type-1 and one type-2 sensor to monitor the second section.
  • Use one type-1 and three type-2 sensors to monitor the third section.

In this case, the total cost of the necessary sensors is 3\times 3 + 2\times 4 = 17, which is the minimum.


Sample Input 2

3
3 5 10
4 3 3
2 2 3

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

5

It is fine if one type of sensor is not used at all.