编码方案还能省多少

难度：T2

【知识点：前缀编码】【知识点：哈夫曼树】

前置知识：字符串、一维数组、循环、函数、树的路径

题目描述

已给出每种符号的正频数和一套合法二元前缀编码。双方共享码表，只比较消息正文的发送位数。允许重新设计前缀编码，请求最多能节省多少位。现有总长度为每种频数乘其码长之和；最优总长度可以用哈夫曼合并得到。输出两者之差，已最优时输出 $0$ 。不要求输出新的码字。

第一行整数 $n$ 。接下来 $n$ 行，每行一个正频数 $w_i$ 和一个非空码字，用空格隔开；第 $i$ 行代表第 $i$ 种符号。码字仅由字符 0、1 组成，保证不同码字互不为前缀，无需验证合法性。

输出一个整数，表示最多能节省的位数。使用可容纳结果的整数类型。

现有长度 $8\times2+4\times2+2\times2+1\times2=30$ ；最优 $3+7+15=25$ ，节省 $5$ 位。

$2\le n\le200$ ， $1\le w_i\le10^6$ ，码字长度 $1$ 到 $200$ 。