Description

However, student XHY does not know how to make a PowerPoint, so she asked the expert CYD for help. She wants to tile $N$ photos of size $4\times 3$ without overlap and without gaps into a single rectangle to use as a background image. For aesthetics, she wants the rectangle’s width and height to be as close as possible (i.e., minimize their absolute difference). Among all arrangements that achieve this minimum difference, the number of rotated photos should be as small as possible. Photos may only be $4\times 3$ (not counted as rotated) or $3\times 4$ (counted as rotated).

Please help CYD write a program to design such an arrangement for XHY that meets these requirements and uses the fewest rotated photos.

Input Format

The first line contains a positive integer $N$.

Output Format

Output a single non‑negative integer — the minimal number of rotated photos.

6

0

7

3

Hint

• For 20% of the testdata, $N \le 10$.
• For 30% of the testdata, $N \le 20$.
• For 50% of the testdata, $N \le 50$.
• For 70% of the testdata, $N \le 233$.
• For 100% of the testdata, $N \le 900$.

Translated by ChatGPT 5