Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Bear and Tower of Cubes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLimak is a little polar bear. He plays by building towers from blocks. Every block is a cube with positive integer length of side. Limak has infinitely many blocks of each side length.

A block with side *a* has volume *a*^{3}. A tower consisting of blocks with sides *a*_{1}, *a*_{2}, ..., *a*_{k} has the total volume *a*_{1}^{3} + *a*_{2}^{3} + ... + *a*_{k}^{3}.

Limak is going to build a tower. First, he asks you to tell him a positive integer *X* — the required total volume of the tower. Then, Limak adds new blocks greedily, one by one. Each time he adds the biggest block such that the total volume doesn't exceed *X*.

Limak asks you to choose *X* not greater than *m*. Also, he wants to maximize the number of blocks in the tower at the end (however, he still behaves greedily). Secondarily, he wants to maximize *X*.

Can you help Limak? Find the maximum number of blocks his tower can have and the maximum *X* ≤ *m* that results this number of blocks.

Input

The only line of the input contains one integer *m* (1 ≤ *m* ≤ 10^{15}), meaning that Limak wants you to choose *X* between 1 and *m*, inclusive.

Output

Print two integers — the maximum number of blocks in the tower and the maximum required total volume *X*, resulting in the maximum number of blocks.

Examples

Input

48

Output

9 42

Input

6

Output

6 6

Note

In the first sample test, there will be 9 blocks if you choose *X* = 23 or *X* = 42. Limak wants to maximize *X* secondarily so you should choose 42.

In more detail, after choosing *X* = 42 the process of building a tower is:

- Limak takes a block with side 3 because it's the biggest block with volume not greater than 42. The remaining volume is 42 - 27 = 15.
- The second added block has side 2, so the remaining volume is 15 - 8 = 7.
- Finally, Limak adds 7 blocks with side 1, one by one.

So, there are 9 blocks in the tower. The total volume is is 3^{3} + 2^{3} + 7·1^{3} = 27 + 8 + 7 = 42.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 19:17:39 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|