{"problem":{"name":"D. Big Maximum Sum","description":{"content":"Ahmed and Mostafa used to compete together in many programming contests for several years. Their coach Fegla asked them to solve one challenging problem, of course Ahmed was able to solve it but Mosta","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF75D"},"statements":[{"statement_type":"Markdown","content":"Ahmed and Mostafa used to compete together in many programming contests for several years. Their coach Fegla asked them to solve one challenging problem, of course Ahmed was able to solve it but Mostafa couldn't.\n\nThis problem is similar to a standard problem but it has a different format and constraints.\n\nIn the standard problem you are given an array of integers, and you have to find one or more consecutive elements in this array where their sum is the maximum possible sum.\n\nBut in this problem you are given _n_ small arrays, and you will create one big array from the concatenation of one or more instances of the small arrays (each small array could occur more than once). The big array will be given as an array of indexes (1-based) of the small arrays, and the concatenation should be done in the same order as in this array. Then you should apply the standard problem mentioned above on the resulting big array.\n\nFor example let's suppose that the small arrays are {1, 6, -2}, {3, 3} and {-5, 1}. And the indexes in the big array are {2, 3, 1, 3}. So the actual values in the big array after formatting it as concatenation of the small arrays will be {3, 3, -5, 1, 1, 6, -2, -5, 1}. In this example the maximum sum is 9.\n\nCan you help Mostafa solve this problem?\n\n## Input\n\nThe first line contains two integers _n_ and _m_, _n_ is the number of the small arrays (1 ≤ _n_ ≤ 50), and _m_ is the number of indexes in the big array (1 ≤ _m_ ≤ 250000). Then follow _n_ lines, the _i_\\-th line starts with one integer _l_ which is the size of the _i_\\-th array (1 ≤ _l_ ≤ 5000), followed by _l_ integers each one will be greater than or equal -1000 and less than or equal 1000. The last line contains _m_ integers which are the indexes in the big array, and you should concatenate the small arrays in the same order, and each index will be greater than or equal to 1 and less than or equal to _n_.\n\nThe small arrays are numbered from 1 to _n_ in the same order as given in the input. Some of the given small arrays may not be used in big array.\n\nNote, that the array is very big. So if you try to build it straightforwardly, you will probably get time or/and memory limit exceeded.\n\n## Output\n\nPrint one line containing the maximum sum in the big array after formatting it as described above. You must choose at least one element for the sum, i. e. it cannot be empty.\n\nPlease, do not use _%lld_ specificator to write 64-bit integers in C++. It is preferred to use _cout_ (also you may use _%I64d_).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ahmed 和 Mostafa 多年来一直一起参加许多编程竞赛。他们的教练 Fegla 要求他们解决一个具有挑战性的问题，当然 Ahmed 能够解决它，但 Mostafa 不能。\n\n这个问题类似于一个标准问题，但具有不同的格式和约束。\n\n在标准问题中，你被给定一个整数数组，你需要找到数组中一个或多个连续元素，使得它们的和是可能的最大和。\n\n但在本问题中，你被给定 #cf_span[n] 个小型数组，你需要通过将一个或多个小型数组的副本按顺序连接来构造一个大数组（每个小型数组可以出现多次）。大数组将由小型数组的索引（1-based）数组给出，连接操作应按照该数组中的顺序进行。然后，你需要对生成的大数组应用上述标准问题。\n\n例如，假设小型数组为 {1, 6, -2}、{3, 3} 和 {-5, 1}，而大数组中的索引为 {2, 3, 1, 3}。那么在将小数组按连接顺序展开后，大数组的实际值为 {3, 3, -5, 1, 1, 6, -2, -5, 1}。在这个例子中，最大和为 9。\n\n你能帮助 Mostafa 解决这个问题吗？\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]，#cf_span[n] 是小型数组的数量（#cf_span[1 ≤ n ≤ 50]），#cf_span[m] 是大数组中索引的数量（#cf_span[1 ≤ m ≤ 250000]）。接下来是 #cf_span[n] 行，第 #cf_span[i] 行以一个整数 #cf_span[l] 开头，表示第 #cf_span[i] 个数组的大小（#cf_span[1 ≤ l ≤ 5000]），后跟 #cf_span[l] 个整数，每个整数的值在 -1000 到 1000 之间（包含端点）。最后一行包含 #cf_span[m] 个整数，表示大数组中的索引，你需要按相同顺序连接对应的小型数组，每个索引满足 1 ≤ 索引 ≤ #cf_span[n]。\n\n小型数组按输入顺序编号为 1 到 #cf_span[n]。某些给定的小型数组可能不会在大数组中被使用。\n\n注意，该数组非常大。因此，如果你尝试直接构建它，可能会导致时间或内存超限。\n\n请输出一行，包含按上述方式格式化后的大数组中的最大和。你必须至少选择一个元素用于求和，即和不能为空。\n\n请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_（也可使用 _%I64d_）。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]，#cf_span[n] 是小型数组的数量（#cf_span[1 ≤ n ≤ 50]），#cf_span[m] 是大数组中索引的数量（#cf_span[1 ≤ m ≤ 250000]）。接下来是 #cf_span[n] 行，第 #cf_span[i] 行以一个整数 #cf_span[l] 开头，表示第 #cf_span[i] 个数组的大小（#cf_span[1 ≤ l ≤ 5000]），后跟 #cf_span[l] 个整数，每个整数的值在 -1000 到 1000 之间（包含端点）。最后一行包含 #cf_span[m] 个整数，表示大数组中的索引，你需要按相同顺序连接对应的小型数组，每个索引满足 1 ≤ 索引 ≤ #cf_span[n]。小型数组按输入顺序编号为 1 到 #cf_span[n]。某些给定的小型数组可能不会在大数组中被使用。注意，该数组非常大。因此，如果你尝试直接构建它，可能会导致时间或内存超限。\n\n## Output\n\n请输出一行，包含按上述方式格式化后的大数组中的最大和。你必须至少选择一个元素用于求和，即和不能为空。请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_（也可使用 _%I64d_）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $:  \n- $ n $: number of small arrays.  \n- $ m $: number of indices in the big array sequence.  \n\nLet $ \\mathcal{A} = (A_1, A_2, \\dots, A_n) $ be a tuple of small arrays, where each $ A_i = (a_{i,1}, a_{i,2}, \\dots, a_{i,\\ell_i}) \\in \\mathbb{Z}^{\\ell_i} $, with $ \\ell_i \\geq 1 $, and $ \\sum_{i=1}^n \\ell_i \\leq 50 \\cdot 5000 $.  \n\nLet $ I = (i_1, i_2, \\dots, i_m) \\in \\{1, 2, \\dots, n\\}^m $ be the sequence of indices specifying the concatenation order of small arrays to form the big array $ B $.  \n\nDefine the big array $ B $ as:  \n$$\nB = A_{i_1} \\oplus A_{i_2} \\oplus \\cdots \\oplus A_{i_m}\n$$  \nwhere $ \\oplus $ denotes concatenation.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50 $  \n2. $ 1 \\leq m \\leq 250000 $  \n3. For each $ i \\in \\{1, \\dots, n\\} $: $ 1 \\leq \\ell_i \\leq 5000 $, and $ -1000 \\leq a_{i,j} \\leq 1000 $  \n4. For each $ k \\in \\{1, \\dots, m\\} $: $ 1 \\leq i_k \\leq n $  \n\n**Objective**  \nCompute the maximum subarray sum of $ B $, i.e.,  \n$$\n\\max_{1 \\leq s \\leq e \\leq |B|} \\sum_{j=s}^{e} B[j]\n$$  \nwhere $ |B| = \\sum_{k=1}^m \\ell_{i_k} $, and **at least one element must be selected**.\n\n**Note**: $ |B| $ may be up to $ 250000 \\cdot 5000 = 1.25 \\times 10^9 $, so explicit construction of $ B $ is infeasible. The solution must operate on the compressed representation $ (I, \\mathcal{A}) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF75D","tags":["data structures","dp","greedy","implementation","math","trees"],"sample_group":[["3 4\n3 1 6 -2\n2 3 3\n2 -5 1\n2 3 1 3","9"],["6 1\n4 0 8 -3 -10\n8 3 -2 -5 10 8 -9 -5 -4\n1 0\n1 -3\n3 -8 5 6\n2 9 6\n1","8"]],"created_at":"2026-03-03 11:00:39"}}