Trie Braiding
Description
Many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. Examples are the trie-based IP lookup and packet classification algorithms. With the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential.
First, we build two original trie tree with single stride.
Then, in order to support the virtual routers, we overlap the two trees.
Can we reduce the total nodes anymore? Yes, we can use the method called Trie Braiding. If we reverse some nodes when overlapping we can reduce more nodes.
All above are based on single-stride tree, but the multiple-stride trees are commonly used in real routers. We take two-stride tree as an example.
In fact, before building the multi-stride tree, we must expand the prefix. For example, the prefix 0(p1) is expanded to 00(p1),01(p1), the prefix 1(p2) is expanded to 10(p2),11(p2), but 10(p3) is already in the original table, so the prefix 10(p2) should be ignored.
Here comes the problem, we give you two prefix tables and the needed stride, please calculated the minimal total nodes you can get after Trie Braiding.
Input
There will be several test cases. In each case, the first line have three integers , m, n, s (0 < m, n < 1000, 0 < s < 6 ), presented the size of two tables and the needed stride. Then follows the two prefix tables in order.
Output
For each test case, the output should contain only one integer, the minimal total nodes.
Samples