描述

派了一群疯狂伊文成功摧毁敌军的碉堡后， L终于得到了他想要的挖掘机，于是开始 情不自禁地挖掘。

L依旧把地面看作连续的 N 个格子。由间谍传回的情报，敌军在这些格子中的每一个 里都埋有一颗地雷，且第 i 格中地雷的种类为 ti。 ti 为一个 1 到 M 之间的整数，并且第 i 类雷 的重量均为 wi。

为了为我军的坦克开辟前进的道路，当然也为了使用自己的挖掘机， L 开始愉快地扫 雷（确切地说是挖雷）。

L会事先选择好 L; R(1 6 L 6 R 6 N)，然后从第 L 个格子出发开到第 R 个格子，边 开边挖地上的雷。 Mr.Lin 喜欢新奇之物，假如当前挖出的雷不与之前挖出的任何一颗雷属于同 一类，他就会把这颗雷收藏起来。否则，他会把地雷拆解回收。

不过， L 现在还没有想好合适的 L 和 R。他的幸运数字是 k，于是希望你帮他选择合 适的 L; R 使得最后收藏的雷的重量之和为所有方案中第 k 大。

输入

第一行两个正整数 N; M 分别表示格子数和地雷的种数。

第二行 M 个正整数 wi。

第三行 N 个正整数 ti。

第四行一个正整数 k，表示L的幸运数字。

输出

第一行一个整数为收藏的雷的总重量。

第二行两个正整数为满足条件的 L 和 R。如果有多个满足条件的 L; R，输出字典序最小的

（即第一关键字为 L，第二关键字为 R）。

样例输入

3 2

1 2

1 2 1

2

样例输出

3

1 2

提示

对于 20% 的数据， N; M <=100。

对于 40% 的数据， N; M <= 1000。

另有 20% 的数据， k <= 10^5。

对于 100% 的数据， 1 <= N; M <= 10^5; 1 <= wi <= 10^9; 1 <= ti <= M; 1 <= k <= (1+N )*N/2

---

一道很好的二分答案。

考虑二分第k个值是val的时候如何检验。

我们可以借用双指针的思想来统计有多少个数不小于val。

然后通过跟k比较来判断是否合法，最后再次使用双指针的思想找到字典序最小的区间就行了。

代码：

#include
    
     #define N 100005#define ll long longusing namespace std;inline ll read(){
     	ll ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}ll w[N],l=0,r=0,k,ret,tot,ans;int pos,col[N],pre[N],n,m;bool in[N];inline ll check(ll val){
     	tot=0,pos=1,ret=0,memset(in,false,sizeof(in)),memset(pre,0,sizeof(pre));	for(int i=1;i<=n;++i){
     		if(pre[col[i]]
     
      =val&&pos<=i)tot-=in[pos]*w[col[pos++]];		ret+=pos-1;	}	return ret;}int main(){
     	n=read(),m=read();	for(int i=1;i<=m;++i)r+=(w[i]=read());	for(int i=1;i<=n;++i)col[i]=read();	k=read();	while(l<=r){
     		ll mid=l+r>>1;		if(check(mid)
      
       ans&&pos<=i)tot-=in[pos]*w[col[pos++]];		if(tot==ans){
     cout<
       
        <<' '<