> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/801-900/821-830/p828.md).

# 828：テンパズル

（原題 Numbers Challenge）

いくつかの数から、目標の数を計算で作る問題は、よく知られた娯楽である。この問題では、6つの数と目標の数が与えられる。

例えば、6つの数 2, 3, 4, 6, 7, 25 と目標の数 211 が与えられたとき、一つの解は：

$$211 = (3 + 6) \times 25 - (4 \times 7) \div 2$$

これは6つの数を全て使っている。しかし、そうする必要はない。7を使わない別解がある：

$$211 = (25 - 2) \times (6 + 3) + 4$$

解に対して、そこで使った数の和をその**コスト**と定義する。上記の例題では、示した二つの解はそれぞれコスト47と40である。この例題はコスト40未満の解は存在しないことがわかる。

計算をするとき、以下の規則を守る必要がある：

* それぞれの数はたかだか一度しか使えない
* 基本の四則演算 $$+, -, \times, \div$$ のみが使える
* 全ての中間結果も正の整数でなければならない。よって例えば $$3 \div 2$$ は部分式として許されない（たとえ最終結果が整数になっても）

入力データ [p828\_number\_challenges.txt](https://projecteuler.net/project/resources/p828_number_challenges.txt) には200の問題が含まれている。1行に1問で以下の形式に従う：

```
211:2,3,4,6,7,25
```

ここで、コロンの前の数が目標で、残りの、コンマ区切りの数が使用できる数である。

問題に $$1,2,\dots,200$$ と番号を順に振り、$$n$$番目の問題の解の最小コストを $$s\_n$$とする。例えば、上記の例題はファイル中の最初の問題なので $$s\_1 = 40$$ である。全ての問題が解を持つ訳ではないことに注意せよ。その場合は $$s\_n = 0$$ とする。

$$\displaystyle \sum\_{n=1}^{200} 3^n s\_n$$ を求めよ。答えは 1005075251 のモジュロで入力せよ。