### Romanian Informatics Olympiad - Modified Huffman Encoding

Source: (Romanian Informatics Olympiad ONI'03, extended team selection) ( ^ Representative diagram of Huffman Encoding. No relevance in the problem) Problem: A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have N<=36 symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in O(N^4) time, and use O(N^3) space.