喜歡做點心餵食小蘿莉的蘿莉農為了精進他的廚藝,特地從世界各地收集了 $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$。
測試資料第一行有兩個正整數 $n, m$,分別代表食材數跟食材搭配數。接下來 $m$ 行,每行會有一個字串 $s_i$ 跟一個整數 $v_i$。如果 $s_i$ 的第 $j$ 個字元是 1
的話代表此搭配中包含第 $j$ 種食材;反之若為 0
的話則代表不包含。而 $v_i$ 則為此搭配的好吃度影響值。
1
請輸出一個整數於一行,代表最好嘗試順序的總好吃度。
2016 NPSC高中組決賽
No. | Testdata Range | Score |
---|---|---|
1 | 0~35 | 100 |