TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

42.1% (24/57)

Description

喜歡做點心餵食小蘿莉的蘿莉農為了精進他的廚藝,特地從世界各地收集了 $n$ 種特級食材。他打算從中挑選一些食材製作成特級餅乾,之後裝進他親手製作的精美餅乾盒中。但要挑選哪些食材好呢?莉農覺得他必須親自嚐過所有可能的非空食材組合,才有辦法從這 $2^ n − 1$種組合中挑出最適合蘿莉食用的餅乾。

我們知道,有些食材是天生絕配,搭在一起會有額外的好吃度加成;而有些食材如果混在一起的話反而會有反效果,甚至是食物中毒。更精確地來說,一個食材搭配是一個集合 s 以及一個好吃度影響值 $v$,如果挑選的食材組合包含 $s$ 的話,其好吃度就會加上 $v$。也就是說一個食材組合的好吃度,就是其所有包含的食材搭配的好吃度總和。舉例來說,如果食材搭配 $(1, 2)$的好吃度影響值是 $3$,而食材搭配 $(2, 3)$ 的好吃度影響值是 $−1$,那麼食材組合 $(1, 2, 3)$ 的好吃度就是 $3 + (−1) = 2$。

蘿莉農嘗試各種組合的同時,他的廚藝熟練度也會逐漸上升。因此若第 i 次的食材組合好吃度是$ d$,則製作出來的餅乾好吃度會是 $i \times d$。為了讓這個試嚐餅乾的過程盡量愉悅而不要從此對餅乾有心理陰影,他希望找一個最好的組合嘗試順序,讓做出來的餅乾總好吃度最大。以上面的例子來說,一種可能的最好嘗試順序為 $(2, 3), (1), (2), (3), (1, 3), (1, 2, 3), (1, 2)$,其總好吃度為 $1 \times −1 + 2 \times 0 + 3 \times 0 + 4 \times 0 + 5 \times 0 + 6 \times 2 + 7 \times 3 = 32$。

Input Format

測試資料第一行有兩個正整數 $n, m$,分別代表食材數跟食材搭配數。接下來 $m$ 行,每行會有一個字串 $s_i$ 跟一個整數 $v_i$。如果 $s_i$ 的第 $j$ 個字元是 1 的話代表此搭配中包含第 $j$ 種食材;反之若為 0 的話則代表不包含。而 $v_i$ 則為此搭配的好吃度影響值。

  • $1\leq n\leq 22$
  • $1\leq m\leq 10^ 5$
  • $\lvert s_i \rvert = n$
  • $s_i$中至少有一個字元為1
  • 所有$s_i$皆相異
  • $-100\leq v_i\leq 100$

Output Format

請輸出一個整數於一行,代表最好嘗試順序的總好吃度。

Sample Input

Sample Input #1
2 2
01 1
10 -1

Sample Input #2
3 2
110 3
011 -1

Sample Output

Sample Output #1
2

Sample Output #2
32

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

For Testdata: 0 ~ 35, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 262144 262144
23 1000 262144 262144
24 1000 262144 262144
25 1000 262144 262144
26 1000 262144 262144
27 1000 262144 262144
28 1000 262144 262144
29 1000 262144 262144
30 1000 262144 262144
31 1000 262144 262144
32 1000 262144 262144
33 1000 262144 262144
34 1000 262144 262144
35 1000 262144 262144