Takahashi's Participation

元ネタ:https://twitter.com/chokudai/status/1556631054722617345

問題文

レベル $L$ の高橋君が $1$ 人居ます。あなたは以下の操作を何回でも行うことが出来ます。

• コストを $C$ ポイント支払い、レベル $X(\geq2)$ の高橋君を $1$ 人選び消滅させ、レベル $X-1$ の高橋君を $2$ 人生成する。

$N$ 社の企業があり、 $i$ 社目の企業にレベル $A_i$ 以上の高橋君が参画すると $B_i$ ポイントの満足度が得られます(レベル $A_i$ 未満の高橋君を参画させることは出来ません)。

また、同じ企業に $2$ 人以上の高橋君を参画させたり、 $1$ 人の高橋君を $2$ つ以上の企業に参画させることは出来ません。

上手く操作および高橋君の割り当てを行うことによって達成できる、 (企業の満足度の総和-支払うコストの総和) の最大値を求めてください。

制約

• $1\leq L \leq 12$
• $0\leq C \leq 10^4$
• $1\leq N \leq 2×10^3$
• $1\leq A_i \leq L$
• $1\leq B_i \leq 10^4$
• 入力は全て整数

入力

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

出力

答えを出力してください。

入力例1

3 3 4
1 1 2 3
3 4 7 7

出力例1

8

例えば以下のように操作を行うと良いです。

• コストを $3$ ポイント支払い、レベル $3$ の 高橋君からレベル $2$ の高橋君 $2$ 人を生成する。
• コストを $3$ ポイント支払い、レベル $2$ の 高橋君からレベル $1$ の高橋君 $2$ 人を生成する。

このように操作を行うと、レベル $2$ の高橋君が $1$ 人とレベル $1$ の高橋君が $2$ 人になります。この高橋君たちを以下のように割り当てます。

• $1$ 人目のレベル $1$ の高橋君を $1$ 社目の企業に参画させ、 $3$ ポイントの満足度を得る。
• $2$ 人目のレベル $1$ の高橋君を $2$ 社目の企業に参画させ、 $4$ ポイントの満足度を得る。
• $1$ 人目のレベル $1$ の高橋君を $3$ 社目の企業に参画させ、 $7$ ポイントの満足度を得る。

得られる満足度の総和は $3+4+7=14$、支払ったコストの総和は $3×2=6$ で、その差は $14-6=8$ です。
これが達成可能な差の最大値です。

入力例2

3 10000 1
1
1

出力例2

1

レベル $3$ の高橋君をそのまま参画させるのが最適です。

入力例3

4 1 8
1 1 1 1 1 1 1 1
1 2 6 11 12 16 2 2

出力例3

45