{"problem":{"name":"[ICPC 2024 Xi'an I] Smart Quality Inspector","description":{"content":"     Ella has a factory. One day, her factory is facing a product quality inspection.                Her factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10561"},"statements":[{"statement_type":"Markdown","content":"Ella has a factory. One day, her factory is facing a product quality inspection.\n    \n    \n    \nHer factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, and the other $K$ lines are unqualified. The fine of the $i$ -th$(1\\leq i\\leq K)$ unqualified line is $i$ Yuan.\n    \n    \n    \nThere are $M$ quality inspectors here. For the $j$ -th$(1\\leq j\\leq M)$ quality inspector, he will inspect from the $l_i$ -th line to the $r_i$ -th line and find the unqualified production line with the largest fine among them, then impose this fine on Ella.\n    \n    \n    \nElla does not want to receive so many fines, so she decides to renumber the $N$ production lines to receive the least amount of fines. Please help her.\n    \n    \n    \nIn simple terms:\n    \n    \n    \nYou have a sequence $A$ of length $N$, $A=[1,2,3,...,K,0,0,0,...,0]$. Here $N,K$ are given.\n    \n    \n    \nThere are $M$ pairs of integers, each pair consists of two numbers $l_i,r_i$.\n    \n    \n    \nYou need to rearrange sequence $A$ to minimize the following:\n    \n    \n    \n$$\\sum_{i=1}^M \\max_{j=l_i}^{r_i} (A_{j})$$\n\n## Input\n\n    \nThe first line contains three integers $N,K,M(1\\leq K\\leq N\\leq 20,1\\leq M\\leq 10^5)$, described in the statement.\n    \n    \n    \nThen $M$ lines, the $i$ -th line of them contains two integers $l_i,r_i(1\\leq l_i\\leq r_i\\leq N)$.\n    \n\n## Output\n\n    \nAn integer indicates the answer.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10561","tags":["2024","O2优化","ICPC","状压 DP","西安"],"sample_group":[["4 4 3\n1 2\n3 4\n1 4","10"]],"created_at":"2026-03-03 11:09:25"}}