{"problem":{"name":"[ICPC 2022 Xi'an R] Streets","description":{"content":"You are given $n$ vertical lines with x-coordinates $x_1, x_2, \\ldots, x_n$ and weights $a_1, a_2, \\ldots, a_n$ and $m$ horizontal lines with y-coordinates $y_1, y_2, \\ldots, y_m$ and weights $b_1, b_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9368"},"statements":[{"statement_type":"Markdown","content":"You are given $n$ vertical lines with x-coordinates $x_1, x_2, \\ldots, x_n$ and weights $a_1, a_2, \\ldots, a_n$ and $m$ horizontal lines with y-coordinates $y_1, y_2, \\ldots, y_m$ and weights $b_1, b_2, \\ldots, b_m$.\n\nCall a rectangle good if and only if all of its four edges lie on the given lines. On this basis, define the cost of a good rectangle as the sum of the costs of its four segments. The cost of a segment is the product of its length and the weight of the line it belongs.\n\nFind the maximum area of good rectangles with cost no more than $c$. Note that the length and the width of the rectangle can be zero, so the answer always exists.\n\nYou need to answer $T$ queries with different $c$.\n\n## Input\n\nThe first line contains three integers $n$, $m$ ($2\\leq n, m\\leq 5\\,000$) and $T$ ($1\\leq T\\leq 100$).\n\nThe second line contains $n$ integers $x_1, x_2, \\ldots, x_n$ ($1\\leq x_1 < x_2 < \\ldots < x_n \\leq 10 ^ 5$).\n\nThe third line contains $n$ integers $a_1, a_2, \\ldots, a_n$ ($1\\leq a_i\\leq 10 ^ 7$).\n\nThe fourth line contains $m$ integers $y_1, y_2, \\ldots, y_m$ ($1\\leq y_1 < y_2 < \\ldots < y_m \\leq 10 ^ 5$).\n\nThe fifth line contains $m$ integers $b_1, b_2, \\ldots, b_m$ ($1\\leq b_i\\leq 10 ^ 7$).\n\nEach of the next $T$ lines contains a single integer $c$ ($1\\leq c\\leq 4\\times 10 ^ {12}$), representing a query.\n\n## Output\n\nFor each query, output one line representing the answer.\n\n[samples]\n\n## Note\n\n**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem K.\n\n**Author**: Alex_Wei.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9368","tags":["2022","O2优化","ICPC","西安"],"sample_group":[["3 4 20\n1 3 4\n3 1 2\n1 3 4 7\n4 2 1 2\n1\n5\n6\n7\n9\n10\n11\n12\n15\n16\n17\n22\n23\n28\n30\n35\n43\n47\n49\n57\n","0\n0\n1\n1\n1\n2\n2\n3\n3\n4\n4\n6\n6\n9\n9\n12\n12\n12\n18\n18\n"]],"created_at":"2026-03-03 11:09:25"}}