AT_arc112_f [ARC112F] Die Siedler

[problemUrl]: https://atcoder.jp/contests/arc112/tasks/arc112_f すぬけくんはカード $ 1 $ からカード $ n $ の $ n $ 種類のカードを使うゲームで遊んでいます。 このゲームには、カードパックが $ m $ 種類存在し、$ i $ 種類目のカードパックにはカード $ j $ が $ s_{i,j} $ 枚含まれています。 どのカードパックにもカードが $ 1 $ 枚以上含まれています。 最初、すぬけくんはカード $ j $ を $ c_j $ 枚持っています（合計で $ 1 $ 枚以上のカードを持っていることが保証されます）。 すぬけくんは、次の操作を好きな順番で好きな回数行うことができます。 - カードパックをもらう：$ i=1,\dots,m $ のうちひとつを選ぶ。$ i $ 種類目のパックに含まれるカードをすべて手に入れる。 - カードを交換する：$ j=1,\dots,n $ のうちひとつを選ぶ。カード $ j $ を $ 2j $ 枚捨てて、カード $ ((j\ \text{\ mod\ }\ n)\ +\ 1) $ を $ 1 $ 枚手に入れる。（カード $ j $ を $ 2j $ 枚以上持っていなければならない。） すぬけくんは持っているカードの総数をできるだけ少なくしたいです。すぬけくんが達成できるカードの総数の最小値を求めてください。

N/A

N/A

### 制約 - $ 2\ \le\ n\ \le\ 16 $ - $ 1\ \le\ m\ \le\ 50 $ - $ 0\ \le\ s_{i,j},\ c_j\ \lt\ 2j $ - $ c_1+\dots\ +c_n\ >\ 0 $ - $ s_{i,1}+\dots\ +s_{i,n}\ >\ 0 $ ### Sample Explanation 1 カード $ 1 $ を $ a_1 $ 枚、カード $ 2 $ を $ a_2 $ 枚、カード $ 3 $ を $ a_3 $ 枚持っていることを $ (a_1,\ a_2,\ a_3) $ と書くことにします。 以下のように操作をすると、カードの総数を $ 1 $ 枚にすることができます。 - $ 1 $ 種類目のカードパックをもらう。$ (0,4,5) $ となる。 - $ j=2 $ を選んでカードを交換する。$ (0,0,6) $ となる。 - $ j=3 $ を選んでカードを交換する。$ (1,0,0) $ となる。 カードの総数を $ 0 $ 枚にすることはできないため、これが最小です。 ### Sample Explanation 2 $ 2 $ 種類目のカードパックを $ 2 $ パックもらったあと、$ 1 $ 種類目のカードパックをもらい、その後何度かカードを交換すると、 カード $ 4 $ とカード $ 5 $ を $ 1 $ 枚ずつ持っている状態が作れます。