TopCoder

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

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

45.2% (33/73)

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

No. Testdata Range Score
1 0~35 100

Testdata and Limits

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