#include <stdio.h>

void chmin(int* a, int b)
{
	if (*a > b) *a = b;
}

int main()
{
	int N;
	scanf("%d", &N);
	
	int i, j, ans[300001];
	for (i = 1; i <= N; i++) ans[i] = i;
	for (i = 1, ans[1] = 0; i < N; i++) for (j = 2; i * j <= N; j++) chmin(&(ans[i*j]), ans[i] + j);
	printf("%d\n", ans[N]);
	fflush(stdout);
	return 0;
}