The Little Match Girl
Once upon a time, a girl named Tanya faced an interesting challenge in her math class. She was tasked with creating K different triangles, each with integer sides, using matches.
Initially, this seemed like an impossible task, especially for large values of K. However, Tanya had a stroke of luck—her father was an avid match collector. He owned numerous boxes of matches, each containing 10^15 matches of the same length. His collection was vast, with exactly one box for every match length L from 1 to 10^10.
Naturally, the value of each box increased with the length of the matches it contained. Tanya wanted to borrow N boxes from her father, and he would give her boxes with match lengths ranging from 1 to N. Because Tanya cherished her father, she aimed to request the fewest number of boxes possible. Your task is to help Tanya determine the minimum number of boxes she needs to ask for.
A triangle can be formed with matches of lengths a ≤ b ≤ c if and only if c < a + b.
Input
An integer K (1 ≤ K ≤ 10^12) - the number of different triangles Tanya needs to create.
Output
An integer N, representing the minimum number of boxes Tanya should request from her father to complete her assignment.