#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct RangeSlide{ vector ls,rs; vector vs; F cmp; RangeSlide(vector vs,F cmp):vs(vs),cmp(cmp){} void add_range(size_t l,size_t r){ ls.emplace_back(l); rs.emplace_back(r); } vector build(){ deque deq; vector res; for(size_t i=0,l=0,r=0;i vector compress(vector v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return v; } template struct FixPoint : F{ FixPoint(F&& f):F(forward(f)){} template decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward(args)...); } }; template inline decltype(auto) MFP(F&& f){ return FixPoint{forward(f)}; } struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; struct Precision{ Precision(){ cout<>n>>d; vector xs(n),ys(n); for(Int i=0;i>xs[i]>>ys[i]; if(n==1){ cout<<(xs[0]<=d?ys[0]:0)<; auto calc= [&](Int a,Int b){ vector

res; MFP([&](auto dfs,Int k,Int s,Int t)->void{ if(k==b){ res.emplace_back(s,t); return; } dfs(k+1,s,t); dfs(k+1,s+xs[k],t+ys[k]); dfs(k+1,s-xs[k],t-ys[k]); })(a,0,0); sort(res.begin(),res.end()); return res; }; auto v1=calc(0,h); auto v2=calc(h,n); reverse(v2.begin(),v2.end()); const Int INF = 1e17; vector vs; for(auto p:v1) vs.emplace_back(p.first); vs.emplace_back(-INF); vs.emplace_back(+INF); vs=compress(vs); vector ws(vs.size(),-INF); { Int k=0; for(auto p:v1){ while(vs[k]b;}; RangeSlide slide(ws,cmp); vector ks; { Int l=0,r=0; for(auto p:v2){ Int x=p.first,k=p.second; while(l<(Int)vs.size()&&vs[l]< -x-d) l++; while(r<(Int)vs.size()&&vs[r]<=-x+d) r++; if(l==r) continue; slide.add_range(l,r); ks.emplace_back(k); } } vs.clear(); v2.clear(); auto res=slide.build(); Int ans=0; for(Int i=0;i<(Int)res.size();i++) chmax(ans,ws[res[i]]+ks[i]); cout<>n>>k; string s; cin>>s; vector a(n); for(int i=0;iint{ vector b(n); for(int i=0;i sm(n*2+1,0); for(int i=0;i rs(sm,cmp); for(int i=0;ism[res[i]]) return 1; return 0; }; D L=0,R=1; for(int k=0;k<20;k++){ D M=(L+R)/2; if(check(M)) L=M; else R=M; } cout<