{"raw_statement":[{"iden":"statement","content":"King Coin IV loves bi-metallic coins. Bi-metallic coins are coins consisting of two different alloys, arranged with an outer ring around a contrasting center. After consulting with the most prominent metallurgists, the king decided to abolish simple coins and increase the use of bi-metallic coins in his country.      \n\nThey have n types of metals. Their technology allows them to mix two different basic metals in equal ratio and produce an alloy. Experienced metallurgists discovered that each alloy has a different thermal area expansion coefficient. For two different alloys, these coefficients help them to determine which one can be used as outer ring in a bi-metallic coin. An alloy can be used as outer ring if its thermal coefficient is less than thermal coefficient of inner part. For each alloy they know the costs to create an outer ring and inner part using that alloy. Because it's very expensive to make a revolution in mediums of exchanges in a country, the king wants to have maximum types of bi-metallic coins with minimum production cost. Note that each alloy can not be used in more than one type of bi-metallic coin.\n\nFirst line contains an integer n (3 ≤ n ≤ 50) — the number of basic metals.   Following 3n lines describe three n × n matrices C, I, O. C consists of real numbers with exactly three digits after the decimal point. Ci, j is thermal area expansion coefficient of alloy composed by metals i and j. \n\nI consists of integers. Ii, j is cost of creating an inner part from alloy composed by metals i and j. (1 ≤ Ii, j ≤ 10000)\n\nO consists of integers. Oi, j is cost of creating an outer ring from alloy composed by metals i and j. (1 ≤ Oi, j ≤ 10000)\n\nC, I, O are symmetric and their diagonals are always zero.\n\nOutput two space separated integers in a single line. The maximum number of bi-metallic coin types and the minimum cost of producing these types while each alloy can not be used in more than one type.\n\n"},{"iden":"input","content":"First line contains an integer n (3 ≤ n ≤ 50) — the number of basic metals.   Following 3n lines describe three n × n matrices C, I, O. C consists of real numbers with exactly three digits after the decimal point. Ci, j is thermal area expansion coefficient of alloy composed by metals i and j. I consists of integers. Ii, j is cost of creating an inner part from alloy composed by metals i and j. (1 ≤ Ii, j ≤ 10000)O consists of integers. Oi, j is cost of creating an outer ring from alloy composed by metals i and j. (1 ≤ Oi, j ≤ 10000)C, I, O are symmetric and their diagonals are always zero."},{"iden":"output","content":"Output two space separated integers in a single line. The maximum number of bi-metallic coin types and the minimum cost of producing these types while each alloy can not be used in more than one type."},{"iden":"examples","content":"Input30.000 0.012 0.3120.012 0.000 0.1110.312 0.111 0.0000 3 53 0 45 4 00 4 94 0 59 5 0Output1 8"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 50 $, be the number of basic metals.  \nLet $ C = (c_{i,j}) \\in \\mathbb{R}^{n \\times n} $, $ I = (i_{i,j}) \\in \\mathbb{Z}^{n \\times n} $, $ O = (o_{i,j}) \\in \\mathbb{Z}^{n \\times n} $ be symmetric matrices with zero diagonals, where:  \n- $ c_{i,j} $ is the thermal expansion coefficient of the alloy formed by metals $ i $ and $ j $,  \n- $ i_{i,j} $ is the cost of forming the inner part from alloy $ (i,j) $,  \n- $ o_{i,j} $ is the cost of forming the outer ring from alloy $ (i,j) $.  \n\nEach alloy $ (i,j) $ with $ i < j $ is a unique unordered pair (since matrices are symmetric and diagonals are zero).  \n\n**Constraints**  \n1. For all $ i,j \\in \\{1,\\dots,n\\} $: $ c_{i,j} = c_{j,i} $, $ i_{i,j} = i_{j,i} $, $ o_{i,j} = o_{j,i} $, and $ c_{i,i} = i_{i,i} = o_{i,i} = 0 $.  \n2. Each alloy $ (i,j) $ with $ i < j $ may be used in at most one bi-metallic coin.  \n3. For a valid bi-metallic coin using alloys $ A = (i,j) $ (inner) and $ B = (k,l) $ (outer):  \n   - $ c_{i,j} > c_{k,l} $ (inner must have higher expansion coefficient than outer).  \n   - The sets of metals used in $ A $ and $ B $ must be disjoint: $ \\{i,j\\} \\cap \\{k,l\\} = \\emptyset $.  \n\n**Objective**  \nFind the maximum number $ m $ of bi-metallic coins that can be produced, and the minimum total cost $ \\sum_{\\text{coin } \\ell} (o_{\\ell} + i_{\\ell}) $, under the above constraints.  \n\nFormally:  \nMaximize $ m $, and subject to that, minimize $ \\sum_{\\ell=1}^m (o_{k_\\ell,l_\\ell} + i_{i_\\ell,j_\\ell}) $,  \nover all sets of $ m $ disjoint pairs $ \\{(i_\\ell,j_\\ell), (k_\\ell,l_\\ell)\\} $, $ \\ell = 1,\\dots,m $, such that:  \n- $ i_\\ell < j_\\ell $, $ k_\\ell < l_\\ell $,  \n- $ \\{i_\\ell,j_\\ell\\} \\cap \\{k_\\ell,l_\\ell\\} = \\emptyset $,  \n- $ c_{i_\\ell,j_\\ell} > c_{k_\\ell,l_\\ell} $.","simple_statement":"You are given n metals. You can make an alloy by mixing any two different metals. Each alloy has a thermal coefficient, and a cost to use it as inner or outer part of a coin.\n\nA bi-metallic coin needs one alloy as inner part and one as outer part, where the outer alloy must have a smaller thermal coefficient than the inner alloy.\n\nEach alloy can be used in at most one coin.\n\nYou want to make as many coins as possible, and among all ways to make the maximum number of coins, choose the one with minimum total cost.\n\nOutput: maximum number of coins and minimum cost to make them.","has_page_source":false}