// Creating a memoization cache for the nmax function
const cache = new Map();

// Defining the nmax function to calculate the maximum number of piles
function nmax(cost) {
  if (cost < 4) return 1;
  if (cache.has(cost)) return cache.get(cost);

  let sum = 0;
  for (let pile = 1; pile <= Math.floor(Math.sqrt(cost)); pile++) {
    sum += nmax(cost - Math.pow(pile, 2));
  }

  cache.set(cost, sum);
  return sum;
}

// Defining the towerBreakers function to find the minimum cost
function towerBreakers(n) {
  for (let cost = 0; ; cost++) {
    if (nmax(cost) >= n) return cost;
  }
}

''' How many stones (maximum) can you fit in for given cost? 
    -> nmax(cost)
    Obviously every pile has to give this same cost, that is 
     -> nmax(cost-1^2) + nmax(cost-2^2)+...
'''

from functools import cache
from itertools import count

@cache
def nmax(cost):
    if cost < 4: return 1
    return sum(nmax(cost-pile**2) 
		                      for pile in range(1,int(math.sqrt(cost))+1))
            
def towerBreakers(n):
    for cost in count():
        if nmax(cost)>=n: return cost