{"problem":{"name":"Interval Counts","description":{"content":"You are given positive integers $x_1, \\ldots, x_N$ such that $x_1 < \\cdots < x_N$, and positive integers $y_1, \\ldots, y_N$. Consider a tuple $(M, L_1, R_1, \\ldots, L_M, R_M)$ that satisfies all of th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc166_d"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $x_1, \\ldots, x_N$ such that $x_1 < \\cdots < x_N$, and positive integers $y_1, \\ldots, y_N$.\nConsider a tuple $(M, L_1, R_1, \\ldots, L_M, R_M)$ that satisfies all of the following conditions.\n\n*   $M$ is a positive integer.\n*   For each $j \\ (1\\leq j\\leq M)$, $L_j$ and $R_j$ are integers such that $L_j\\leq R_j$.\n*   For each $i \\ (1\\leq i\\leq N)$, exactly $y_i$ integers $j \\ (1\\leq j\\leq M)$ satisfy $L_j\\leq x_i\\leq R_j$.\n\nIt can be proved that such a tuple always exists. Find the maximum value of $\\min \\lbrace R_j-L_j\\mid 1\\leq j\\leq M\\rbrace$ for such a tuple. If there is no maximum value, print `-1`.\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq x_1 < \\cdots < x_N \\leq 10^9$\n*   $1\\leq y_i \\leq 10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $\\cdots$ $x_N$\n$y_1$ $\\cdots$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc166_d","tags":[],"sample_group":[["3\n1 3 5\n1 3 1","2\n\nFor example, we have $\\min \\lbrace R_j-L_j\\mid 1\\leq j\\leq M\\rbrace = 2$ for the tuple $(3, 1, 4, 2, 4, 3, 5)$."],["3\n1 10 100\n2 3 2","\\-1\n\nFor example, we have $\\min \\lbrace R_j-L_j\\mid 1\\leq j\\leq M\\rbrace = 990$ for the tuple $(3, -1000, 10, -1000, 1000, 10, 1000)$. There is no maximum value of $\\min \\lbrace R_j-L_j\\mid 1\\leq j\\leq M\\rbrace$."],["7\n10 31 47 55 68 73 90\n3 7 4 6 3 4 4","56"]],"created_at":"2026-03-03 11:01:14"}}