// ////////////////////////////////////////////////////////
// # Title
// Almost Pi
//
// # URL
// https://projecteuler.net/problem=461
// http://euler.stephan-brumme.com/461/
//
// # Problem
// Let `f_n(k) = e^{k/n} - 1`, for all non-negative integers `k`.
//
// Remarkably, `f_200(6) + f_200(75) + f_200(89) + f_200(226) = 3.141592644529 ... approx pi`.
//
// In fact, it is the best approximation of `pi` of the form `f_n(a) + f_n(b) + f_n(c) + f_n(d)` for `n = 200`.
//
// Let `g(n) = a^2 + b^2 + c^2 + d^2` for `a`, `b`, `c`, `d` that minimize the error: `|f_n(a) + f_n(b) + f_n(c) + f_n(d) - pi|`
// (where `|x|` denotes the absolute value of `x`).
//
// You are given `g(200) = 6^2 + 75^2 + 89^2 + 226^2 = 64658`.
//
// Find `g(10000)`.
//
// # Solved by
// Stephan Brumme
// September 2017
//
// # Algorithm
// I tried to find the result with a randomized genetic search but failed because I was always stuck in local minimums - and finally gave up.
//
// Surprisingly, pretty much everybody else solved the problem with something similar to my current approach:
// - create all pairs `f_10000(a) + f_10000(b)`
// - for each such pair find a second pair `f_10000(c) + f_10000(d)` such that `|f_10000(a) + f_10000(b) + f_10000(c) + f_10000(d) - pi|` is minimized
//
// The upper limit for `a`, `b`, `c`, `d` is 14211 because `e^{14211/10000} - 1 > pi`.
// I can assume pair-wise that `a < b` and `c < d` without loss of generality.
// Therefore I have to analyze up to `T(14211) = 14211 * 14210 / 2 = 100969155` pairs.
// However, the sum of a few pairs exceeds `pi` so that only `72299877` pairs need to be considered (see container ''pairs'').
//
// To find the optimal partner for each ''pairs[i]'' I perform a binary search for ''PI - pairs[i]''.
// That's the same concept I used in solving problem 266 (and in problem 152).
//
// The STL's ''std::upper_bound'' returns the first value that is too large. This number and its predecessor need to be analyzed.
// If their error is less than before then I remember their indices ''left'' and ''right''.
//
// The final step is to map ''left'' and ''right'' back to ''a'', ''b'', ''c'', ''d''.
// Maybe there is a smarter way than just two nested loops - but they are pretty fast, so that's okay for me.
//
// # Alternative
// I'm quite worried that I exceed the memory limit of 256 MByte: my program needs about 640 MByte.
// After submitting my result to the Project Euler forum I saw that a clever use of priority queues could reduce memory consumption from `O(n^2)` to `O(n)`.
// Those guys are brilliant !
//
// I thought a while about a segmented algorithm, where ''pairs'' represents only a part of all pairs.
// Thus I could stay within the 256 MByte limit at the expense of a severely increased execution time.
// However, the main reason against such an approach is that the code would increase a lot, too, and readability suffer massively.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

const double PI = 3.1415926535897932;

int main()
{
  // example was n = 200, problem asks for n = 10000
  unsigned int order = 10000;
  std::cin >> order;

  // find maximum value such that e^(maximum/n) - 1 <= PI
  // ... and while at it: store all values in f
  std::vector<double> f;
  unsigned int maximum = 0;
  while (true)
  {
    auto current = exp(maximum / double(order)) - 1;
    // too large ?
    if (current > PI)
      break;

    f.push_back(current);
    maximum++;
  }

  // generate all pairs f[i] + f[j] <= PI (with i <= j)
  std::vector<double> pairs;
  pairs.reserve(maximum * maximum / 10); // some heuristic to avoid too frequent allocations
  for (size_t i = 0; i < maximum; i++)
    for (size_t j = i; j < maximum; j++)
    {
      // abort, sum exceeds 3.1415
      if (f[i] + f[j] > PI)
        break;

      pairs.push_back(f[i] + f[j]);
    }

  // sort all values
  //std::sort(pairs.begin(), pairs.end());
  // a bit faster: compare double as 64 bit integers => works on CPU, not FPU
  // only possible because all values are positive and there are no NaN or other special values
  std::sort(pairs.begin(), pairs.end(), [] (double a, double b)
                                      {
                                        // cast from 64 bit double to 64 bit integer
                                        auto aa = (const long long*) &a;
                                        auto bb = (const long long*) &b;
                                        return *aa < *bb;
                                      });

  // optimal value for f_a + f_b
  size_t left  = 0;
  // optimal value for f_c + f_d
  size_t right = 0;
  // minimize error |f_a + f_b - PI|
  double minError  = PI;
  for (size_t i = 0; i < pairs.size(); i++)
  {
    // binary search for the best match
    auto current = pairs[i];
    auto need    = PI - current;
    if (need < current) // same as need < PI/2
      break;

    // this value and its predecessor are candidates
    auto match = std::upper_bound(pairs.begin(), pairs.end(), need); // actually "sums.begin() + i" works, too

    // "match" is a value slightly too large
    auto error = fabs(need - *match);
    if (error < minError)
    {
      minError = error;
      left  = i;
      right = std::distance(pairs.begin(), match);
    }

    // now "match" is a value slightly too small (or an exact match => spoiler alert: there is no perfect match)
    match--;
    error = fabs(need - *match);
    if (error < minError)
    {
      minError = error;
      left  = i;
      right = std::distance(pairs.begin(), match);
    }
  }

  // resolve the left pair f_a and f_b
  unsigned int result = 0;
  bool resolvedLeft = false;
  for (size_t a = 0; a < maximum && !resolvedLeft; a++)
    for (size_t b = a; b < maximum; b++)
      if (pairs[left]  == f[a] + f[b])
      {
        result += a*a + b*b;
        resolvedLeft  = true;
        break;
      }

  // resolve the left pair f_c and f_d
  bool resolvedRight = false;
  for (size_t c = 0; c < maximum && !resolvedRight; c++)
    for (size_t d = c; d < maximum; d++)
      if (pairs[right] == f[c] + f[d])
      {
        result += c*c + d*d;
        resolvedRight = true;
        break;
      }

  std::cout << result << std::endl;
  return 0;
}