Problem
ハンサム ジャックは、自分のエリジウム処理工場を立ち上げたいと考えています。
ジャックの管理下に n 個の工場があり、それぞれに 1 から n までの番号が付けられています。各植物はエリジウム鉱床にあり、そこでも組み合わせて採掘されます。また、工場番号が大きいほど新しいものです。
各プラントには効率指数 a
i があります。正、負、ゼロのいずれかです。
各プラントはエリジウム鉱石を処理する必要があります。パイプラインを介して、独自の預金を使用するか、過去に別のプラントで処理された鉱石を取得できます。ただし、このプロセスには多少の制限があります。第 1 に、パイプライン システムに過負荷がかからないようにするために、各プラントは、鉱石をさらに処理するために厳密に相互に受け入れることができます (または、独自の鉱床を受け入れて使用しないでください)。第二に、古いプラントは、新しいプラントの後に鉱石を再処理する技術的能力がありません.
システム全体の最終的なパフォーマンスは、次のように計算されます。各プラントについて、その効率 a
i に処理段階を掛けます。処理段階は、入ってくる鉱石が処理される回数として計算されます。 (詳しくは例題の説明を参照してください)、取得したすべての値をすべての植物についてまとめます。
システム全体の全体的なパフォーマンスが可能な限り高くなるように、ハンサム ジャックがシステムを整理するのを手伝ってください。
入力:
最初の行には、工場の数である自然数 n (1 <= n <= 7) が含まれています。
2 行目にはスペースで区切られた n 個の整数が含まれ、i 番目の数値は a
i (-1000 <= a
i <= 1000) - 基本効率
出力:
単一の数値を出力します。これは、システム全体で可能な最大の合計パフォーマンスです。
例:
<本体>
| 入力 |
出力 |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
説明:
最初の例では、最初のプラントが独自の鉱石を採掘し、2 番目のプラントが最初のプラントから鉱石を受け取り、3 番目のプラントが 2 番目のプラントから鉱石を受け取ることが最も収益性が高くなります。この場合、第 1 工場は一次処理を行い、その生産性は 1 * 1 = 1 です。第 2 工場は二次処理を行い、その生産性は 5 * 2 = 10 です。そして、第 3 工場は受け取った鉱石を 3 回目に処理します。その生産性は 3 * 3 = 9 です。合計のパフォーマンスは 1 + 10 + 9 = 20 です。
この例では、2 番目と 3 番目のプラントを交換できないことに注意してください。 2 番目のプラントは、3 番目よりも古いため、技術的な理由で 3 番目以降の鉱石を処理できません。
2 番目の例では、1 番目と 3 番目の工場は鉱床を使用し、2 番目の工場は最初の工場から鉱石を受け取ります。