Frog In The Well

2 secs 1024 MB
sgsw

問題文


とある学園都市には、つの学校が存在します。

それぞれの学校において以下の問題を解いてください。


学校には人の生徒と何人かの教員が在籍している。

番目の生徒は「能力値」,「幸福値」を持っている。

全員の生徒の能力値は互いに相異なる。

今から、人の生徒をクラス分けによって異なるクラスに所属させたい。

クラスの個数は任意であるが、各クラスには、人以上の生徒が在籍し、加えて所属するメンバーの番号は昇順に並べた時連続でなくてはいけない。(※)

こうしてできたそれぞれのクラスにおいて、最も能力値の高い生徒の幸福値はそのままであるが、それ以外の同クラスのメンバーの幸福値はになってしまう

また、クラスをつ作ることに教員の負担が増える。なお、教員の負担の初期値はである。

「学校としての幸福値」を「全生徒の幸福値」から「教員の負担」を引いた値とする時、「学校としての幸福値の最大値」はいくつか。

のように生徒の列をいくつかの連続部分列に分けるということを指す


制約


・テストケースは個与えられる。

◎全てのテストケースに対して以下が成り立つ。

(すなわちの要素はいずれも互いに相異なる)

・入力は全て整数値である。

◉テストケース全体を通して以下が成り立つ。

個のテストケースにおけるの総和は以下である

入力


はじめに = (テストケースの数)が与えられる。

その後回にわたって,番目の学校のデータが与えられる。

各学校のデータは以下の形式で与えられる。

N C
A_1 ... A_N
B_1 ... B_N

テストケース全体での入力は以下で与えられる。

T
N_1 C_1
A_1 ... A_{N_1}
B_1 ... B_{N_1}
N_2 C_2
A_1 ... A_{N_2}
B_1 ... B_{N_2}
.
.
.
N_T C_T
A_1 ... A_{N_T}
B_1 ... B_{N_T}

出力


全部で行出力してください。

行目には、番目の学校の最大の幸福値を出力してください。

最後に改行してください。

サンプル


入力1
2
4 0
15 22 7 8
10 2 9 7
4 5
10 1 6 2
2 1 6 3
出力1
28
-2

つ目の学校において、クラスを増やすことによる教員の負担値はです。

この場合、学校の幸福値は生徒の幸福値に依存するので、できるだけ全員の生徒を幸福にする必要があります。

明らかに、各生徒を異なるクラスに在籍させると、全生徒が幸福です。この時、全生徒の幸福値はであり、学校としての幸福値の最大値もこの値になります。

よってを出力します。

つ目の学校において、クラスを増やすことによる教員の負担値はです。 この場合、学校の幸福値は生徒の幸福値と教員の幸福値に依存します。

番目の生徒をクラスに、番目の生徒をクラスに所属させることにします。

この時、クラスで最も能力値の高い生徒と、クラスで最も能力値の高い生徒の幸福値の合計値が全生徒の幸福値となります。

クラスはつ存在するため、教員の負担はとなり、学校としての幸福値の最大値はになります。

学校としての幸福値をこれ以上上げることは不可能であるため、を出力します。

入力2
2
5 5
27 16 10 24 34
10 3 1 8 6
5 1
26 15 11 5 25
4 9 5 8 10
出力2
9
31

つ目の学校においては、[(),(),()]あるいは[(),(),()]のようにクラスを構成すると学校全体の幸福値としてを得ます。

つ目の学校においては、[(),(),(),(),()]のようにクラスを構成すると学校全体の幸福値としてを得ます。

入力3
2
5 6
9 4 17 12 14
5 9 3 1 8
5 4
20 14 7 11 4
1 9 10 8 2
出力3
1
12

つ目の学校においては、[(),(),(),()]のようにクラスを構成すると学校全体の幸福値としてを得ます。

つ目の学校においては、[(),(),(),()]のようにクラスを構成すると学校全体の幸福値としてを得ます。

入力4
2
20 3
71 8 51 89 34 24 87 70 44 32 77 31 28 74 61 62 65 54 18 96
4 8 3 4 9 9 8 7 1 5 5 4 10 8 3 2 10 2 4 3
20 9
111 33 50 112 95 10 72 27 78 57 45 101 8 41 65 93 40 21 18 85
8 9 6 4 3 10 6 7 8 4 9 8 7 6 8 5 7 3 10 3
出力4
53
-5

Submit


Go (1.14)