CF679B Bear and Tower of Cubes

Limak 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

The only line of the input contains one integer $ m $ ( $ 1

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.

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 $ .