using System; using System.IO; using System.Collections.Generic; using System.Globalization; using System.Linq; using System.Text; using E = System.Linq.Enumerable; partial class Solver { const int Mod = 1000000007; public void Run() { var N = ni(); var primeSet = new PrimeSet(1263); var factor = primeSet .Select(p => GetFactor(p, N)) .Where(p => p.Count > 0) .ToArray(); var f1 = factor.Where(f => f.Count >= 2).ToArray(); var f2 = factor.Where(f => f.Count < 2).ToArray(); var M = f1.Length; var maxV = new int[1 << M]; var vList = E.Range(0, 1 << M).Select(_ => new List()).ToArray(); for (int i = 1; i <= N; i++) { var v = i; int flags = 0; for (int j = 0; j < f1.Length; j++) { var p = f1[j].Prime; if (v % p == 0) { flags |= (1 << j); while (v % p == 0) v /= p; } } if (v > 1) continue; maxV[flags] = i; vList[flags].Add(i); } var dp1 = new int[1 << M]; for (int i = 1; i < dp1.Length; i++) { dp1[i] = int.MinValue; for (int j = i; j > 0; j = (j - 1) & i) { var pre = i ^ j; dp1[i] = Math.Max(dp1[i], dp1[pre] + maxV[j]); } } var dp2 = new int[1 << M]; foreach (var p in f2) { var next = new int[1 << M]; for (int i = 0; i < dp2.Length; i++) { next[i] = dp2[i] + p.Prime; for (int j = i; j > 0; j = (j - 1) & i) { var v = vList[j].Select(x => x * p.Prime) .Where(x => x <= N) .DefaultIfEmpty(0) .Max(); next[i] = Math.Max(next[i], dp2[i ^ j] + v); } } dp2 = next; } long ans = 0; for (int i = 0; i < (1 << M); i++) { ans = Math.Max(ans, dp1[i] + dp2[((1 << M) - 1) ^ i]); } cout.WriteLine(ans); } Factor GetFactor(int prime, int N) { int cnt = 0; long x = prime; while (x <= N) { x *= prime; cnt++; } return new Factor { Prime = prime, Count = cnt }; } struct Factor { public int Prime { get; set; } public int Count { get; set; } } } public class PrimeSet : List { private readonly bool[] isPrime; public PrimeSet(int size) : base() { isPrime = Enumerable.Repeat(true, size).ToArray(); Add(2); for (int i = 3; i <= size; i += 2) { if (!isPrime[i >> 1]) continue; Add(i); for (long j = (long)i * i; j <= size; j += i + i) isPrime[j >> 1] = false; } } public bool IsPrime(long x) { if (x == 2) return true; if (x <= 1 || x % 2 == 0) return false; return isPrime[x >> 1]; } } // PREWRITEN CODE BEGINS FROM HERE partial class Solver : Scanner { public static void Main(string[] args) { #if LOCAL new Solver(Console.In, Console.Out).Run(); #else Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(Console.In, Console.Out).Run(); Console.Out.Flush(); #endif } #pragma warning disable IDE0052 private readonly TextReader cin; private readonly TextWriter cout; #pragma warning restore IDE0052 public Solver(TextReader reader, TextWriter writer) : base(reader) { this.cin = reader; this.cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } #pragma warning disable IDE1006 #pragma warning disable IDE0051 private int ni() { return NextInt(); } private int[] ni(int n) { return NextIntArray(n); } private long nl() { return NextLong(); } private long[] nl(int n) { return NextLongArray(n); } private double nd() { return NextDouble(); } private double[] nd(int n) { return NextDoubleArray(n); } private string ns() { return Next(); } private string[] ns(int n) { return NextArray(n); } #pragma warning restore IDE1006 #pragma warning restore IDE0051 } public static class LinqPadExtension { static public T Dump(this T obj) { #if LOCAL return LINQPad.Extensions.Dump(obj); #else return obj; #endif } } public class Scanner { private readonly TextReader Reader; private readonly Queue TokenQueue = new Queue(); private readonly CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { this.Reader = reader; } public int NextInt() { return int.Parse(Next(), ci); } public long NextLong() { return long.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { var array = new string[size]; for (int i = 0; i < size; i++) array[i] = Next(); return array; } public int[] NextIntArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = NextInt(); return array; } public long[] NextLongArray(int size) { var array = new long[size]; for (int i = 0; i < size; i++) array[i] = NextLong(); return array; } public double[] NextDoubleArray(int size) { var array = new double[size]; for (int i = 0; i < size; i++) array[i] = NextDouble(); return array; } public string Next() { if (TokenQueue.Count == 0) { if (!StockTokens()) throw new InvalidOperationException(); } return TokenQueue.Dequeue(); } public bool HasNext() { if (TokenQueue.Count > 0) return true; return StockTokens(); } static readonly char[] _separator = new[] { ' ' }; private bool StockTokens() { while (true) { var line = Reader.ReadLine(); if (line == null) return false; var tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) continue; foreach (var token in tokens) TokenQueue.Enqueue(token); return true; } } }