### Problem Statement

In the Kocurkovo village there is a shop that sells simple planar graphs. (See Notes for a definition.)

The cost of any graph with X vertices and Y edges is (X^3 + Y^2) gold coins.

Monika has N gold coins, and she wants to spend all of them on simple planar graphs.

Write a method that gets the value N and computes the minimum number of simple planar graphs Monika has to buy in order to spend exactly N gold coins. She is allowed to buy multiple graphs of the same type.

### Definition

 Class: PlanarGraphShop Method: bestCount Parameters: int Returns: int Method signature: int bestCount(int N) (be sure your method is public)

### Notes

-A simple graph is an ordered pair (V,E) where V is a finite non-empty set of objects called vertices, and E is a finite set of edges. Each edge is a two-element subset of V.

(You can find drawings of several graphs in Example #3.)
-Note that a simple graph does not contain any loops (edges that connect a vertex to itself) and any duplicate edges. In other words, each edge connects two different vertices, and each pair of vertices is connected by at most one edge.
-A graph is called planar if it has a drawing in the plane such that no two edges intersect.
-Note that a simple planar graph does not have to be connected.

### Constraints

-N will be between 1 and 50,000, inclusive.

### Examples

0)

 `36`
`Returns: 1`
 For 36 gold coins she can buy a triangle: a simple planar graph with 3 vertices and 3 edges.
1)

 `7`
`Returns: 7`
 The only simple planar graph that costs 7 gold coins or less is the graph that consists of a single vertex (and no edges). This graph costs 1^3 + 0^2 = 1, so Monika has to buy 7 of them.
2)

 `72`
`Returns: 2`
 She can buy 2 triangles for 36 gold coins each. No simple planar graph costs exactly 72 gold coins, hence the optimal answer in this case is 2.
3)

 `46`
`Returns: 3`
 All the graphs Monika can afford are shown in the following picture: One optimal solution is to buy graphs worth 1 + 9 + 36 gold coins.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10412

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14174&pm=10412

misof

#### Testers:

PabloGilberto , Yarin , ivan_metelsky

#### Problem categories:

Dynamic Programming, Graph Theory