#include using namespace std; // #define int long long using ll=long long; using vi=vector; using vl=vector; using pii=pair; using pll=pair; #define ITR(v,c) for(auto v=begin(c);v!=end(c);v++) #define FORE(x,c) for(auto &x:c) #define FOR(v,a,n) for(int v=a;v<(int)(n);v++) #define REP(v,n) FOR(v,0,n) #define RREP(v,n) for(int v=((int)(n)-1);v>=0;v--) #define ALL(c) begin(c),end(c) #define RALL(c) rbegin(c),rend(c) #define SZ(c) ((int)c.size()) const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0}; const int INF=1e9; const long long INFLL=1e18; template ostream& operator << (ostream &os, const vector &v) { ITR(i,v) os<<*i<<(i==end(v)-1?"":"\n"); return os; } template istream& operator >> (istream &is, vector &v) { ITR(i,v) is>>*i; return is; } //------------------------------------------------------------------------------ int dp[10000]; inline bool check(int bits,int index) { return (bits&(1<>str; vector a; for(char x:str) a.push_back(x-'0'); int N=str.size(); int ans=0; for(int S=0; S<=(1<