No.719 Coprime

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 19
作問者 : startcppstartcpp / テスター : butsurizukibutsurizuki
2 ProblemId : 1074 / 出題時の順位表

問題文

うさぎは、$2$~$N$の数字が書かれたカードを$1$枚ずつ、合計$N - 1$枚用意しました。
うなぎは、その中からカードを好きなだけ選びます。
うなぎがカードを選び終えると、うさぎは、うなぎが選んだカードの組み合わせに応じてお金を渡します。

具体的には、
うなぎが選んだカードに書かれた値の集合を$U$としたとき、$U$のどの異なる$2$つの値も互いに素であれば、
うさぎは「うなぎが選んだカードに書かれた値の合計」[円]のお金を(うなぎに)渡します。

うなぎがもらえる金額を$X$[円]としたとき、$X$の最大値を求めてください。

入力

N

$2 \le N \le 1262$

出力

$X$の最大値を$1$行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
6
出力
12

うさぎは$2$,$3$,$4$,$5$,$6$の書かれたカードを$1$枚ずつ用意しています。
うなぎは、「$3$が書かれたカード, $4$が書かれたカード, $5$が書かれたカード」を選ぶことで、もらえる金額を最大化できます。
このとき得られる金額は、$3 + 4 + 5 = 12$円です。

しかし、「$4$が書かれたカード, $5$が書かれたカード, $6$が書かれたカード」を全て選んだ場合、お金はもらえません。
これは、$4$と$6$が互いに素ではない(最大公約数が$1$にならない)からです。

サンプル2
入力
2
出力
2

カードを$1$枚だけ選んでもお金をもらうことができます。

サンプル3
入力
18
出力
79

例えば、${7, 11, 13, 15, 16, 17}$の書かれたカード($6$枚)を選ぶことで、$79$円のお金をもらうことができます。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。