D. Exams
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 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.
On 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.
About each subject Vasiliy know a number ai — 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 ai days for the exam number i. He can mix the order of preparation for exams in any way.
Your 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.
Input
The 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.
The second line contains n integers d1, d2, …, dn (0 ≤ di ≤ m), where di is the number of subject, the exam of which can be passed on the day number i. If di equals 0, it is not allowed to pass any exams on the day number i.
The third line contains m positive integers a1, a2, …, am (1 ≤ ai ≤ 105), where ai is the number of days that are needed to prepare before passing the exam on the subject i.
Output
Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.
Examples
input
7 2
0 1 0 2 1 0 2
2 1
output
5
input
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4
output
9
input
5 1
1 1 1 1 1
5
output
-1
Note
In 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.
In 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.
In the third example Vasiliy can’t pass the only exam because he hasn’t anough time to prepare for it.U5923 期末考试
翻译提供wanjiaxu
题目背景
亨远是个毒奶，这一点从你们进了复赛这一点就可以看出来。
题目描述
期末考试来了，作为一名神牛兼毒奶，亨远理应是要考前抱佛脚的。
大学的考试不同于高中，现在亨远有着n天的考期。在这n天中，亨远要考完m课考试，显然，每门课亨远都是要复（自）习（学）的。
同时，亨远可以预估出如果他要通过一门考试，他大概要复习多少天。注意，亨远一天能且只能复习一门，而且，每一门的考试都要花费他整整一天的时间，这意味着考试那天他是不能复习的。不过，亨远用不着连续的复习同一门学科，只要复习的总天数到了，那么他就可以通过他所复习的学科的考试。
现在，亨远给你每门学科考试的时间，和每个学科他要复习的时间。注意，一门学科可以考多次试，而且亨远可以选择不去参加某一天的考试，但到最后必须他每一门考试都有分。现在他想让你算出他通过所有考试的最短时间，这样他就可以尽快回家。
至于他为什么不自己算，当然是因为毒奶啊。
输入输出格式
输入格式：
第一行是两个整数，n和m。表示n天的考期与一共有m个学科。
第二行是n个整数，d1，d2……dn，di表示第i天有一个di学科的考试，如果di为0，表示那一天没有考试。
第三行是m个整数，s1，s2……sm，si表示第i个学科亨远要复习si天。
输出格式：
一个整数k，表示亨远通过所有考试的最短时间。如果通过不了，输出-1。
输入输出样例
输入样例#1：
7 2
0 1 0 2 1 0 2
2 1
输出样例#1：
5
输入样例#2：
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4
输出样例#2：
9
输入样例#3：
5 1
1 1 1 1 1
5
输出样例#3：
-1
说明
对于30%数据，0
/*
二分答案+贪心检验.
检验的时候先处理出在当前天数下最后考试的时间.
然后贪心检验即可.
*/
#include<iostream>
#include<cstdio>
#define MAXN 100001
using namespace std;
int s[MAXN],a[MAXN],n,m,max1[MAXN],maxt[MAXN],ans;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
bool check(int x)
{
int tot=0,total=0;
for(int i=1;i<=x;i++) max1[i]=0,maxt[i]=0;
for(int i=x;i>=1;i--) max1[a[i]]=max(max1[a[i]],i);
for(int i=1;i<=x;i++)
if(max1[a[i]]!=i||!a[i]) maxt[i]=maxt[i-1]+1;
else maxt[i]=maxt[i-1],total++;
if(total<m) return false;
for(int i=1;i<=x;i++)
{
if(a[i]&&max1[a[i]]==i)
{
if(s[a[i]]<=maxt[i]-tot) tot+=s[a[i]];
else return false;
}
}
return true;
}
void erfen(int l,int r)
{
int mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(!ans) printf("-1");
else printf("%d",ans);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) s[i]=read();
erfen(1,n);
return 0;
}