Copiado al portapapeles
Descripción
Las elecciones se acercan y, por tanto, se está probando un nuevo sistema "democrático" de votación. Desde luego, como el partido que propuso este sistema no cuenta con gente que los apoye, deben calcular la mínima cantidad de votos que deben comprar (con el dinero del gobierno) o tener para ganar las elecciones.
El nuevo sistema funciona de la siguiente manera. Se puede dividir las elecciones en etapas en las que se vota por representantes de manera recursiva o simplemente se puede votar en ese momento por uno de los candidatos.
En cada etapa hay un grupo de $N$ personas de las cuales una o más se postula para ser un representante de ese grupo.
1) Si se realiza una votación directa todos votan y quien tiene más votos será elegido representante de ese grupo.
2) Si realiza la votación de manera recursiva se debe dividir el grupo de $N$ personas en $M$ grupos de exactamente $G$ personas cada uno ($N=M*G$). Con los representantes de cada uno de estos grupos se realiza una votación directa.
El gobierno puede decidir cómo dividir los grupos, organizar las etapas e indicar qué personas pertenecen a qué grupo de la manera que más les convenga. El representante elegido para el grupo de todas las personas será desde luego el presidente. Calcular la mínima cantidad de personas que deben votar a favor del gobierno para que su candidato sea ganador de las elecciones.
Entrada
La cantidad total de personas $N$.
Límites
$1 \leq N \leq 10000$
Salida
La mínima cantidad de personas.
Ejemplo Entrada
9
Ejemplo Salida
4