#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #define inf 0x7fffffff #define T 10000 using namespace std; inline 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-'0';ch=getchar();} return x*f; } struct edge{int to,next,v;}e[200001]; int n,cnt=1,s,ans,head[10001],h[10001]; inline void ins(int u,int v,int w){ <span style="white-space:pre"> </span>e[++cnt]=(edge){v,head[u],w};head[u]=cnt; <span style="white-space:pre"> </span>e[++cnt]=(edge){u,head[v],0};head[v]=cnt; } inline bool bfs(){ <span style="white-space:pre"> </span>int t=0,w=0,now,q[20001]; <span style="white-space:pre"> </span>memset(h,-1,sizeof(h)); <span style="white-space:pre"> </span>h[0]=q[0]=0; <span style="white-space:pre"> </span>while(t<=w){ <span style="white-space:pre"> </span>now=q[t++]; <span style="white-space:pre"> </span>for(int i=head[now];i;i=e[i].next){ <span style="white-space:pre"> </span>if(e[i].v&&h[e[i].to]==-1){ <span style="white-space:pre"> </span>h[e[i].to]=h[now]+1; <span style="white-space:pre"> </span>q[++w]=e[i].to; <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>if(h[T]==-1)return 0; <span style="white-space:pre"> </span>else return 1; } inline int dfs(int x,int f){ <span style="white-space:pre"> </span>if(x==T)return f; <span style="white-space:pre"> </span>int used=0,rest; <span style="white-space:pre"> </span>for(int i=head[x];i;i=e[i].next){ <span style="white-space:pre"> </span>if(e[i].v&&h[e[i].to]==h[x]+1){ <span style="white-space:pre"> </span>rest=f-used; <span style="white-space:pre"> </span>rest=dfs(e[i].to,min(e[i].v,rest)); <span style="white-space:pre"> </span>e[i].v-=rest; <span style="white-space:pre"> </span>e[i^1].v+=rest; <span style="white-space:pre"> </span>used+=rest; <span style="white-space:pre"> </span>if(used==f)return f; <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>if(!used)h[x]=-1; <span style="white-space:pre"> </span>return used; } int main(){ <span style="white-space:pre"> </span>freopen("balla.in","r",stdin); <span style="white-space:pre"> </span>freopen("balla.out","w",stdout); <span style="white-space:pre"> </span>n=read(); <span style="white-space:pre"> </span>while(1){ <span style="white-space:pre"> </span>ans++,s++; <span style="white-space:pre"> </span>for(int i=1;i<s;i++) <span style="white-space:pre"> </span>if(sqrt(i+s)==(int)(sqrt(i+s))) <span style="white-space:pre"> </span>ins(i,s+5000,1); <span style="white-space:pre"> </span>ins(0,s,1);ins(s+5000,T,1); <span style="white-space:pre"> </span>while(bfs())ans-=dfs(0,inf); <span style="white-space:pre"> </span>if(ans>n)break; <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>printf("%d\n",s-1); <span style="white-space:pre"> </span>return 0; }