{"raw_statement":[{"iden":"statement","content":"Adilbek's house is located on a street which can be represented as the OX axis. This street is really dark, so Adilbek wants to install some post lamps to illuminate it. Street has $n$ positions to install lamps, they correspond to the integer numbers from $0$ to $n - 1$ on the OX axis. However, some positions are blocked and no post lamp can be placed there.\n\nThere are post lamps of different types which differ only by their power. When placed in position $x$, post lamp of power $l$ illuminates the segment $[x; x + l]$. The power of each post lamp is always a positive integer number.\n\nThe post lamp shop provides an infinite amount of lamps of each type from power $1$ to power $k$. Though each customer is only allowed to order post lamps of _exactly one_ type. Post lamps of power $l$ cost $a_l$ each.\n\nWhat is the minimal total cost of the post lamps of _exactly one_ type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street? If some lamps illuminate any other segment of the street, Adilbek does not care, so, for example, he may place a lamp of power $3$ in position $n - 1$ (even though its illumination zone doesn't completely belong to segment $[0; n]$)."},{"iden":"input","content":"The first line contains three integer numbers $n$, $m$ and $k$ ($1 \\le k \\le n \\le 10^6$, $0 \\le m \\le n$) — the length of the segment of the street Adilbek wants to illuminate, the number of the blocked positions and the maximum power of the post lamp available.\n\nThe second line contains $m$ integer numbers $s_1, s_2, \\dots, s_m$ ($0 \\le s_1 &lt; s_2 &lt; \\dots s_m &lt; n$) — the blocked positions.\n\nThe third line contains $k$ integer numbers $a_1, a_2, \\dots, a_k$ ($1 \\le a_i \\le 10^6$) — the costs of the post lamps."},{"iden":"output","content":"Print the minimal total cost of the post lamps of _exactly one_ type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street.\n\nIf illumintaing the entire segment $[0; n]$ is impossible, print _\\-1_."},{"iden":"examples","content":"Input\n\n6 2 3\n1 3\n1 2 3\n\nOutput\n\n6\n\nInput\n\n4 3 4\n1 2 3\n1 10 100 1000\n\nOutput\n\n1000\n\nInput\n\n5 1 5\n0\n3 3 3 3 3\n\nOutput\n\n\\-1\n\nInput\n\n7 4 3\n2 4 5 6\n3 14 15\n\nOutput\n\n\\-1"}],"translated_statement":[{"iden":"statement","content":"Adilbek 的房子位于一条可以表示为 OX 轴的街道上。这条街道非常黑暗，因此 Adilbek 希望安装一些路灯来照亮它。街道上有 $n$ 个可以安装路灯的位置，对应 OX 轴上的整数 $0$ 到 $n -1$。然而，某些位置被阻塞，无法安装路灯。\n\n商店提供不同类型的路灯，这些路灯仅在功率上有所不同。当将功率为 $l$ 的路灯安装在位置 $x$ 时，它会照亮区间 $[ x \\; x + l ]$。每个路灯的功率均为正整数。\n\n商店提供无限数量的功率从 $1$ 到 $k$ 的路灯。但每位顾客只能订购恰好一种类型的路灯。功率为 $l$ 的路灯每个成本为 $a_l$。\n\nAdilbek 购买恰好一种类型的路灯，使得整个街道区间 $[ 0 \\; n ]$ 被照亮的最小总成本是多少？如果某些路灯照亮了街道以外的区域，Adilbek 并不在意，因此例如他可以在位置 $n -1$ 安装一个功率为 $3$ 的路灯（即使其照明区域并未完全包含在区间 $[ 0 \\; n ]$ 内）。\n\n第一行包含三个整数 $n$、$m$ 和 $k$（$1 \\leq k \\leq n \\leq 10^6$，$0 \\leq m \\leq n$）——分别表示 Adilbek 想要照亮的街道段长度、被阻塞位置的数量以及可用路灯的最大功率。\n\n第二行包含 $m$ 个整数 $s_1, s_2, \\dots, s_m$（$0 \\leq s_1 < s_2 < \\dots < s_m < n$）——被阻塞的位置。\n\n第三行包含 $k$ 个整数 $a_1, a_2, \\dots, a_k$（$1 \\leq a_i \\leq 10^6$）——路灯的成本。\n\n请输出 Adilbek 购买恰好一种类型的路灯以照亮整个区间 $[ 0 \\; n ]$ 的最小总成本。\n\n如果无法照亮整个区间 $[ 0 \\; n ]$，请输出 _-1_。"},{"iden":"input","content":"第一行包含三个整数 $n$、$m$ 和 $k$（$1 \\leq k \\leq n \\leq 10^6$，$0 \\leq m \\leq n$）——分别表示 Adilbek 想要照亮的街道段长度、被阻塞位置的数量以及可用路灯的最大功率。第二行包含 $m$ 个整数 $s_1, s_2, \\dots, s_m$（$0 \\leq s_1 < s_2 < \\dots < s_m < n$）——被阻塞的位置。第三行包含 $k$ 个整数 $a_1, a_2, \\dots, a_k$（$1 \\leq a_i \\leq 10^6$）——路灯的成本。"},{"iden":"output","content":"请输出 Adilbek 购买恰好一种类型的路灯以照亮整个区间 $[ 0 \\; n ]$ 的最小总成本。如果无法照亮整个区间 $[ 0 \\; n ]$，请输出 _-1_。"},{"iden":"examples","content":"输入\n6 2 3\n1 3\n1 2 3\n输出\n6\n\n输入\n4 3 4\n1 2 3\n1 10 100 1000\n输出\n1000\n\n输入\n5 1 5\n3 3 3 3 3\n输出\n-1\n\n输入\n7 4 3\n2 4 5 6\n3 14 15\n输出\n-1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n \\in \\mathbb{N} $: length of the segment to illuminate, $[0, n]$.\n- Let $ m \\in \\mathbb{N}_0 $: number of blocked positions.\n- Let $ k \\in \\mathbb{N} $: maximum lamp power available, $ 1 \\leq k \\leq n $.\n- Let $ B \\subseteq \\{0, 1, \\dots, n-1\\} $: set of blocked positions, $ |B| = m $, with $ B = \\{s_1, s_2, \\dots, s_m\\} $, $ s_1 < s_2 < \\dots < s_m $.\n- Let $ a_l \\in \\mathbb{N} $: cost of one lamp of power $ l $, for $ l = 1, 2, \\dots, k $.\n\n**Constraints:**\n\n- Lamps can only be placed at integer positions $ x \\in \\{0, 1, \\dots, n-1\\} \\setminus B $.\n- A lamp of power $ l $ placed at position $ x $ illuminates the interval $ [x, x + l] $.\n- All lamps installed must be of the same power $ l \\in \\{1, 2, \\dots, k\\} $.\n- The entire segment $ [0, n] $ must be covered: $ \\bigcup_{i} [x_i, x_i + l] \\supseteq [0, n] $.\n- Lamps may extend beyond $ n $; only coverage of $ [0, n] $ is required.\n\n**Objective:**\n\nFind  \n$$\n\\min_{\\substack{l \\in \\{1, \\dots, k\\} \\\\ \\text{and } l \\text{ is feasible}}} \\left( \\left\\lceil \\frac{n}{l} \\right\\rceil \\cdot a_l \\right)\n$$  \n**if** a valid covering exists for lamp power $ l $, else $ -1 $.\n\n**Feasibility condition for power $ l $:**\n\nLet $ \\text{coverable}(l) $ be true if and only if it is possible to place lamps of power $ l $ at unblocked positions such that $ [0, n] $ is covered.\n\nTo compute feasibility:\n\n- Define $ \\text{next}[i] $: the rightmost position reachable by placing a lamp at or before position $ i $, avoiding blocked positions.\n- Use greedy coverage: start at $ 0 $, and at each step, from current position $ p $, find the rightmost unblocked position $ x \\leq p $ such that $ x + l > p $. If no such $ x $ exists, coverage is impossible.\n- Alternatively, simulate coverage:  \n  Let $ \\text{curr} = 0 $.  \n  While $ \\text{curr} < n $:  \n    - Find the largest $ x \\in \\{0, 1, \\dots, \\min(\\text{curr}, n-1)\\} \\setminus B $ such that $ x + l > \\text{curr} $.  \n    - If no such $ x $ exists → impossible.  \n    - Else, set $ \\text{curr} = x + l $.  \n  If $ \\text{curr} \\geq n $, feasible.\n\nBut for efficiency (since $ n \\leq 10^6 $), precompute for each $ l \\in [1, k] $ whether coverage is possible using a greedy algorithm with a precomputed array of next available positions.\n\n**Efficient feasibility check per $ l $:**\n\nPrecompute an array $ \\text{max\\_reach}[i] $ for $ i = 0 $ to $ n $:  \n- $ \\text{max\\_reach}[i] = \\max \\{ x + l \\mid x \\leq i, x \\notin B \\} $, if $ x \\in [0, n-1] $, else $ -\\infty $.\n\nActually, better: Precompute an array $ \\text{next\\_avail}[i] $: for each position $ i \\in [0, n-1] $, let $ \\text{next\\_avail}[i] $ be the largest position $ \\leq i $ that is not blocked. If none, $ -\\infty $.\n\nThen for fixed $ l $, simulate:\n\n- $ \\text{pos} = 0 $\n- While $ \\text{pos} < n $:\n  - Let $ x = \\text{next\\_avail}[\\text{pos}] $ (i.e., the rightmost unblocked position $ \\leq \\text{pos} $)\n  - If $ x = -\\infty $ or $ x + l \\leq \\text{pos} $: impossible\n  - Else: $ \\text{pos} = x + l $\n\nBut note: we can place a lamp at any unblocked position $ \\leq \\text{pos} $, so to maximize coverage, we should choose the rightmost unblocked position $ \\leq \\text{pos} $, say $ x $, and then new coverage is $ x + l $.\n\nSo define:\n\nLet $ R[i] = \\max \\{ j \\in [0, i] \\setminus B \\} $, for $ i = 0 $ to $ n-1 $.  \nIf no such $ j $, $ R[i] = -1 $.\n\nThen for lamp power $ l $:\n\n- $ \\text{current} = 0 $\n- While $ \\text{current} < n $:\n  - $ x = R[\\text{current}] $\n  - If $ x = -1 $ or $ x + l \\leq \\text{current} $: return false\n  - Else: $ \\text{current} = x + l $\n\nReturn true if $ \\text{current} \\geq n $\n\n**Final Objective:**\n\n$$\n\\min_{l=1}^{k} \\left\\{ \n\\begin{array}{ll}\na_l \\cdot \\left\\lceil \\frac{n}{l} \\right\\rceil & \\text{if } \\text{feasible}(l) \\\\\n\\infty & \\text{otherwise}\n\\end{array}\n\\right.\n$$\n\nThen output $ \\min $ if finite, else $ -1 $.\n\nBut note: the number of lamps is **not** $ \\lceil n/l \\rceil $, because coverage may require overlapping or non-uniform placement due to blocked positions. The minimal number of lamps needed for power $ l $ is determined by the greedy algorithm above, not by $ \\lceil n/l \\rceil $.\n\nSo the total cost for power $ l $ is: $ a_l \\times (\\text{number of lamps used in optimal greedy placement}) $\n\nLet $ c(l) $ = minimal number of lamps of power $ l $ needed to cover $ [0, n] $, using greedy algorithm over unblocked positions.\n\nThen:\n\n$$\n\\boxed{\n\\min_{l=1}^{k} \\left\\{ a_l \\cdot c(l) \\mid \\text{feasible}(l) \\right\\}\n}\n$$\n\nIf no $ l \\in \\{1,\\dots,k\\} $ is feasible, output $ -1 $.\n\n---\n\n**Formal Statement:**\n\nLet $ n, k \\in \\mathbb{N} $, $ m \\in \\mathbb{N}_0 $, $ B \\subseteq \\{0, 1, \\dots, n-1\\} $, $ |B| = m $, $ a_1, \\dots, a_k \\in \\mathbb{N} $.\n\nDefine for each $ l \\in \\{1, \\dots, k\\} $:\n\n- Let $ R[i] = \\max \\left( \\{ j \\in [0, i] \\setminus B \\} \\cup \\{ -1 \\} \\right) $ for $ i = 0, 1, \\dots, n-1 $.\n- Initialize $ \\text{pos} = 0 $, $ \\text{count} = 0 $.\n- While $ \\text{pos} < n $:\n  - If $ R[\\text{pos}] = -1 $ or $ R[\\text{pos}] + l \\leq \\text{pos} $: set $ c(l) = \\infty $, break.\n  - Else: $ \\text{pos} \\leftarrow R[\\text{pos}] + l $, $ \\text{count} \\leftarrow \\text{count} + 1 $.\n- Set $ c(l) = \\text{count} $ if $ \\text{pos} \\geq n $, else $ \\infty $.\n\nThen:\n\n$$\n\\boxed{\n\\min_{l=1}^{k} a_l \\cdot c(l)\n}\n\\quad \\text{if} \\quad \\min_{l=1}^{k} c(l) < \\infty, \\quad \\text{else} \\quad \\boxed{-1}\n$$","simple_statement":null,"has_page_source":false}