Description
Consider some square matrix A with side n consisting of zeros and ones. There are n rows numbered from 1 to n from top to bottom and n columns numbered from 1 to n from left to right in this matrix. We'll denote the element of the matrix which is located at the intersection of the i-row and the j-th column as Ai, j.
Let's call matrix A clear if no two cells containing ones have a common side.
Let's call matrix A symmetrical if it matches the matrices formed from it by a horizontal and/or a vertical reflection. Formally, for each pair (i, j) (1 ≤ i, j ≤ n) both of the following conditions must be met: Ai, j = An - i + 1, j and Ai, j = Ai, n - j + 1.
Let's define the sharpness of matrix A as the number of ones in it.
Given integer x, your task is to find the smallest positive integer n such that there exists a clear symmetrical matrix A with side n and sharpness x.
Input
The only line contains a single integer x (1 ≤ x ≤ 100) — the required sharpness of the matrix.
Output
Print a single number — the sought value of n.
Sample Input
4
3
9
5
Hint
The figure below shows the matrices that correspond to the samples:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int main()
{
int n;
cin >> n;
if(n==1)
{
cout << "1" <<endl;
return 0;
}
if(n==2)
{
cout << "3" <<endl;
return 0;
}
if(n==3)
{
cout << "5" <<endl;
return 0;
}
if(n%4==0)
{
n/=4;
for(int i=1;i<=1000000;i++)
{
n -= i;
if(n<=0)
{
cout << i*2+1 <<endl;
return 0;
}
}
}
if(n%4==1)
{
n/=4;
for(int i=1;i<=1000000;i++)
{
n -= i;
if(n<=0)
{
cout << i*2+1 <<endl;
return 0;
}
}
}
if(n%4==2)
{
for(int i=1;i<=1000000;i++)
{
n -= i*4;
if(n<=0)
{
cout << i*2+1 <<endl;
return 0;
}
}
}
if(n%4==3)
{
n--;
for(int i=1;i<=1000000;i++)
{
n -= i*4;
if(n<=0)
{
cout << i*2+1 <<endl;
return 0;
}
}
}
return 0;
}