J - Rental Office
問題文
寺子さんは、レンタルオフィスを 1 つ借りて競技プログラミング大会を開催しようとしています。寺子さんはレンタルオフィスを借りる予算として $M$ 円を用意しています。 $M$ 円以内で借りることのできるレンタルオフィスの中で、最も高い料金を支払うレンタルオフィスを借りようと考えています。
寺子さんはレンタルオフィスを $R$ 箇所調べました。 $i$ 番目 $(1 \le i \le R)$ のレンタルオフィスの部屋の広さは $S_i$ 平方メートルです。$i$ 番目のレンタルオフィスの料金 $C_i$ は次の式で計算されます。
$$C_i = \sum_{k=1}^{R} \left\lfloor \sqrt{S_i + S_k} \right\rfloor$$
ここで、 $\lfloor x \rfloor$ は $x$ 以下の最大の整数を表し、 $\lfloor \sqrt{x} \rfloor$ は $x$ の平方根の整数部分を表します。例えば、 $\lfloor \sqrt{10} \rfloor = 3$ です。
入力は、広さ列が広義単調増加 $(S_1 \le S_2 \le \dots \le S_R)$ となるように与えられます。
このとき、 $M$ 円以内で借りることのできるレンタルオフィスの中で、最も高い料金を求めてください。条件を満たすレンタルオフィスが存在しない場合は -1 を出力してください。
制約
- $1 \le M \le 10^9$
- $1 \le R \le 6\times10^5$
- $1 \le S_i \le 10^6~~(1\le i \le R)$
- $S_1 \le S_2 \le \dots \le S_R$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$M~~R$
$S_1~~$$S_2~~$$\dots$$~~S_R$
出力
予算内で借りることのできるレンタルオフィスの料金の最大値を出力せよ。条件を満たすレンタルオフィスが存在しない場合は -1 を出力せよ。
8 3
1 4 9
7
各レンタルオフィスの料金は次の通りです。
- $C_1 = \lfloor \sqrt{1+1} \rfloor + \lfloor \sqrt{1+4} \rfloor + \lfloor \sqrt{1+9} \rfloor = 1 + 2 + 3 = 6$
- $C_2 = \lfloor \sqrt{4+1} \rfloor + \lfloor \sqrt{4+4} \rfloor + \lfloor \sqrt{4+9} \rfloor = 2 + 2 + 3 = 7$
- $C_3 = \lfloor \sqrt{9+1} \rfloor + \lfloor \sqrt{9+4} \rfloor + \lfloor \sqrt{9+9} \rfloor = 3 + 3 + 4 = 10$
$C_1$ と $C_2$ が予算内なので、その中で最大の料金である $C_2 = 7$ が答えになります。
10 2
100 200
-1
各レンタルオフィスの料金は次の通りです。
- $C_1 = \lfloor \sqrt{100+100} \rfloor + \lfloor \sqrt{100+200} \rfloor = 14 + 17 = 31$
- $C_2 = \lfloor \sqrt{200+100} \rfloor + \lfloor \sqrt{200+200} \rfloor = 17 + 20 = 37$
どちらのレンタルオフィスも予算を超過しているため、 -1 を出力します。