{"raw_statement":[{"iden":"statement","content":"There is an undirected weighted complete graph of $n$ vertices where $n$ is odd.\n\nLet's define a _cycle-array_ of size $k$ as an array of edges $[ e_1, e_2, \\\\dots, e_k ]$ that has the following properties: \n\nIt is obvious that edges in a cycle-array form a cycle.\n\nLet's define $f (e_1, e_2)$ as a function that takes edges $e_1$ and $e_2$ as parameters and returns the maximum between the weights of $e_1$ and $e_2$.\n\nLet's say that we have a cycle-array $C = [ e_1, e_2, \\\\dots, e_k ]$. Let's define the _price of a cycle-array_ as the sum of $f (e_i, e_{i + 1})$ for all $i$ from $1$ to $k$ (consider $e_{k + 1} = e_1$). \n\nLet's define a _cycle-split_ of a graph as a set of non-intersecting cycle-arrays, such that the union of them contains all of the edges of the graph. Let's define the _price of a cycle-split_ as the sum of prices of the arrays that belong to it. \n\nThere might be many possible cycle-splits of a graph. Given a graph, your task is to find the cycle-split with the minimum price and print the price of it.\n\nThe first line contains one integer $n$ ($3 <= n <= 999$, $n$ is odd) — the number of nodes in the graph.\n\nEach of the following $frac(n dot.op (n -1), 2)$ lines contain three space-separated integers $u$, $v$ and $w$ ($1 <= u, v <= n, u eq.not v, 1 <= w <= 10^9$), meaning that there is an edge between the nodes $u$ and $v$ that has weight $w$.\n\nPrint one integer — the minimum possible price of a cycle-split of the graph.\n\nLet's enumerate each edge in the same way as they appear in the input. I will use $e_i$ to represent the edge that appears $i$-th in the input.\n\nThe only possible cycle-split in the first sample is $S = {[ e_1, e_2, e_3 ]}. \" \"f (e_1, e_2) + f (e_2, e_3) + f (e_3, e_1) = 1 + 1 + 1 = 3$.\n\nThe optimal cycle-split in the second sample is $S = {[ e_3, e_8, e_9 ], [ e_2, e_4, e_7, e_{10}, e_5, e_1, e_6 ]}$. The price of $[ e_3, e_8, e_9 ]$ is equal to $12$, the price of $[ e_2, e_4, e_7, e_{10}, e_5, e_1, e_6 ]$ is equal to $23$, thus the price of the split is equal to $35$.\n\n"},{"iden":"input","content":"The first line contains one integer $n$ ($3 <= n <= 999$, $n$ is odd) — the number of nodes in the graph.Each of the following $frac(n dot.op (n -1), 2)$ lines contain three space-separated integers $u$, $v$ and $w$ ($1 <= u, v <= n, u eq.not v, 1 <= w <= 10^9$), meaning that there is an edge between the nodes $u$ and $v$ that has weight $w$."},{"iden":"output","content":"Print one integer — the minimum possible price of a cycle-split of the graph."},{"iden":"examples","content":"Input3\n1 2 1\n2 3 1\n3 1 1\nOutput3Input5\n4 5 4\n1 3 4\n1 2 4\n3 2 3\n3 5 2\n1 4 3\n4 2 2\n1 5 4\n5 2 4\n3 4 2\nOutput35"},{"iden":"note","content":"Let's enumerate each edge in the same way as they appear in the input. I will use $e_i$ to represent the edge that appears $i$-th in the input.The only possible cycle-split in the first sample is $S = {[ e_1, e_2, e_3 ]}. \" \"f (e_1, e_2) + f (e_2, e_3) + f (e_3, e_1) = 1 + 1 + 1 = 3$.The optimal cycle-split in the second sample is $S = {[ e_3, e_8, e_9 ], [ e_2, e_4, e_7, e_(10), e_5, e_1, e_6 ]}$. The price of $[ e_3, e_8, e_9 ]$ is equal to $12$, the price of $[ e_2, e_4, e_7, e_(10), e_5, e_1, e_6 ]$ is equal to $23$, thus the price of the split is equal to $35$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of files.  \nLet $ x \\in \\mathbb{Z}^+ $ be the size (in GB) of each file.  \nLet $ a \\in \\mathbb{Z}^+ $ be the capacity (in GB) of each flash memory.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 10^5 $,  \n$ 1 \\leq x \\leq a \\leq 10^5 $.  \n\n**Objective**  \nCompute the minimum number of flash memories required to store all $ n $ files, where each file must be stored entirely in one flash memory, and no flash memory can exceed capacity $ a $.  \n\nLet $ k = \\left\\lfloor \\frac{a}{x} \\right\\rfloor $ be the maximum number of files that can be stored in one flash memory.  \nThen the minimum number of flash memories needed is:  \n$$\n\\left\\lceil \\frac{n}{k} \\right\\rceil\n$$","simple_statement":"You have n files, each of size x GB.  \nEach flash memory can hold up to a GB.  \nYou cannot split a file across memories.  \nFind the minimum number of flash memories needed to store all files.","has_page_source":false}