The
Company
There are N
people working in a company. Every person is employed in one of the departments
of the company and is either a BOSS
or a simple EMPLOYEE. Every boss
interacts with every employee in his department (but not with other bosses). The
degree of efficiency of a department is equal to the number of distinct
interactions (boss,employee) which take place in that
department. The efficiency of the whole company is the sum of the degrees of
efficiency of every department.
The manager of the company knows that the efficiency of
the company is E. However, in order for it to be a relevant proof of good
management, the efficiency has to be achieved using a minimal number of
persons. If the efficiency can be achieved in more than one way, with the same
minimal number of persons, then the total number of bosses in the company has
to be minimum.
You have to find the minimum number of persons N and the
minimum number of bosses S with whom the efficiency E can be achieved. Plus,
you have to determine the structure of the company, specifying the number of
departments and for every department, the total number of people working in
that department (including the bosses) and the number of bosses working there.
Input
Data
In the input file COMP.IN there will
be a single integer: E.
Output
Data
The first line of the output file COMP.OUT will contain
the numbers N,S and K, separated by blanks, meaning
the minimum number of people, the minimum number of bosses and the number of
departments of the company. On the next K lines, there will be 2 integers: Pi
and Si, separated by a blank, representing the number of people working in the
department #i and the number of bosses (if there are Si bosses, then there wil
be Pi-Si simple employees in that department). If there are more solutions for
the structure of the company, then you can print any of them.
Limits:
·
1 <= E <= 2000
·
The company must have at least one department.
·
S1+S2+..+Sk=S
Example
COMP.IN COMP.OUT
7 7
3 2
2
1
5
2
Time limit: 1 second/test
case