{"problem":{"name":"D. Exams","description":{"content":"Vasiliy has an exam period which will continue for _n_ days. He has to pass exams on _m_ subjects. Subjects are numbered from 1 to _m_. About every day we know exam for which one of _m_ subjects can ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF732D"},"statements":[{"statement_type":"Markdown","content":"Vasiliy has an exam period which will continue for _n_ days. He has to pass exams on _m_ subjects. Subjects are numbered from 1 to _m_.\n\nAbout every day we know exam for which one of _m_ subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day.\n\nOn each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest.\n\nAbout each subject Vasiliy know a number _a__i_ — the number of days he should prepare to pass the exam number _i_. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during _a__i_ days for the exam number _i_. He can mix the order of preparation for exams in any way.\n\nYour task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105) — the number of days in the exam period and the number of subjects.\n\nThe second line contains _n_ integers _d_1, _d_2, ..., _d__n_ (0 ≤ _d__i_ ≤ _m_), where _d__i_ is the number of subject, the exam of which can be passed on the day number _i_. If _d__i_ equals 0, it is not allowed to pass any exams on the day number _i_.\n\nThe third line contains _m_ positive integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 105), where _a__i_ is the number of days that are needed to prepare before passing the exam on the subject _i_.\n\n## Output\n\nPrint one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print _\\-1_.\n\n[samples]\n\n## Note\n\nIn the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.\n\nIn the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day.\n\nIn the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasiliy 有一个持续 #cf_span[n] 天的考试周期。他需要通过 #cf_span[m] 门科目的考试。科目编号从 1 到 #cf_span[m]。\n\n对于每一天，我们知道可以在该天通过哪一门 #cf_span[m] 科目的考试。可能有些天无法通过任何考试。不允许在同一天通过多门考试。\n\n每天 Vasiliy 可以选择：通过当天的考试（占用一整天），或全天准备某门科目的考试，或休息。\n\n对于每门科目，Vasiliy 知道一个数字 #cf_span[ai] —— 通过第 #cf_span[i] 门科目考试所需的准备天数。Vasiliy 在准备过程中可以切换科目，不需要连续 #cf_span[ai] 天为第 #cf_span[i] 门科目准备。他可以任意安排各科目的准备顺序。\n\n你的任务是确定 Vasiliy 通过所有考试所需的最少天数，或判断这是不可能的。每门考试必须恰好通过一次。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 105]）——考试周期的天数和科目数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn]（#cf_span[0 ≤ di ≤ m]），其中 #cf_span[di] 表示在第 #cf_span[i] 天可以参加考试的科目编号。如果 #cf_span[di] 等于 0，则第 #cf_span[i] 天不允许参加任何考试。\n\n第三行包含 #cf_span[m] 个正整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 105]），其中 #cf_span[ai] 表示通过第 #cf_span[i] 门科目考试所需的准备天数。\n\n请输出一个整数——Vasiliy 通过所有考试所需的最少天数。如果不可能，输出 _-1_。\n\n在第一个例子中，Vasiliy 可以这样安排：前两天准备科目 1 的考试，并在第五天通过；第三天准备科目 2 的考试，并在第四天通过。\n\n在第二个例子中，Vasiliy 应该在前四天准备科目 3 的考试，并在第五天通过；第六天准备科目 2 的考试，并在第七天通过；之后在第八天准备科目 1 的考试，并在第九天通过。\n\n在第三个例子中，Vasiliy 无法通过唯一的考试，因为他没有足够的时间准备。 \n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 105]）——考试周期的天数和科目数量。第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn]（#cf_span[0 ≤ di ≤ m]），其中 #cf_span[di] 表示在第 #cf_span[i] 天可以参加考试的科目编号。如果 #cf_span[di] 等于 0，则第 #cf_span[i] 天不允许参加任何考试。第三行包含 #cf_span[m] 个正整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 105]），其中 #cf_span[ai] 表示通过第 #cf_span[i] 门科目考试所需的准备天数。\n\n## Output\n\n请输出一个整数——Vasiliy 通过所有考试所需的最少天数。如果不可能，输出 _-1_。\n\n[samples]\n\n## Note\n\n在第一个例子中，Vasiliy 可以这样安排：前两天准备科目 1 的考试，并在第五天通过；第三天准备科目 2 的考试，并在第四天通过。\n\n在第二个例子中，Vasiliy 应该在前四天准备科目 3 的考试，并在第五天通过；第六天准备科目 2 的考试，并在第七天通过；之后在第八天准备科目 1 的考试，并在第九天通过。\n\n在第三个例子中，Vasiliy 无法通过唯一的考试，因为他没有足够的时间准备。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of days and subjects, respectively.  \nLet $ D = (d_1, d_2, \\dots, d_n) \\in \\{0, 1, \\dots, m\\}^n $ be the sequence where $ d_i $ is the subject exam available on day $ i $, or $ 0 $ if no exam is available.  \nLet $ A = (a_1, a_2, \\dots, a_m) \\in \\mathbb{Z}^+^m $ be the preparation requirements, where $ a_i $ is the number of days needed to prepare for subject $ i $.  \n\nLet $ P \\subseteq \\{1, \\dots, n\\} $ be the set of days on which an exam is taken.  \nLet $ \\text{prep}_i \\in \\mathbb{Z}_{\\geq 0} $ be the total number of days allocated to preparation for subject $ i $ before its exam day.  \n\n**Constraints**  \n1. For each subject $ i \\in \\{1, \\dots, m\\} $, there exists exactly one day $ j \\in \\{1, \\dots, n\\} $ such that $ d_j = i $ and $ j \\in P $ (each exam taken exactly once).  \n2. For each subject $ i \\in \\{1, \\dots, m\\} $, $ \\text{prep}_i \\geq a_i $.  \n3. Preparation days for subject $ i $ must occur before its exam day $ j $, i.e., all days $ k < j $ with $ d_k = 0 $ or $ d_k \\neq i $ can be used for prep.  \n4. On each day $ j $, Vasiliy performs at most one action: take an exam (if $ d_j > 0 $), prepare for some subject, or rest.  \n5. If $ d_j = 0 $, no exam can be taken; only prep or rest is allowed.  \n\n**Objective**  \nFind the minimum $ k \\in \\{1, \\dots, n\\} $ such that all $ m $ exams can be passed by day $ k $, satisfying all constraints.  \nIf no such $ k $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF732D","tags":["binary search","greedy","sortings"],"sample_group":[["7 2\n0 1 0 2 1 0 2\n2 1","5"],["10 3\n0 0 1 2 3 0 2 0 1 2\n1 1 4","9"],["5 1\n1 1 1 1 1\n5","\\-1"]],"created_at":"2026-03-03 11:00:39"}}