1994 ACM Student Programming Contest

Pacific Region

Problem G: Nodes and Wires

Suppose we have N nodes and M wires.  Wires can be used to
establish connections between nodes, subject to the
constraints that
  
  (1)  a given pair of nodes may be directly connected by
       at most one wire;
  
  (2)  both ends of a wire must connect to a node; and
  
  (3)  a wire cannot have both its ends connected to the
       same node.

We define the degree of a given node i, denoted deg(i), to
be the number of wires connected to the node i.  A certain
application requires connecting a set of N nodes with M
wires in such a way that all M wires are used and further
that the value of the expression

             S  =  sum from i=1 to N {deg(i)**2}
                              
is maximized.  Your task is to write a program which, given
pairs of values N and M, will determine the maximum possible
value of S for each pair.

The input to your program will be a file containing a series
of lines.  Each line contains two integer values, N and then
M, separated by one or more spaces and followed by end of
line. Neither N nor M will exceed 20,000.

The output of your program is to be a single line for each
input data line, giving the maximum possible value for the
above expression S if all the wires can be used, or giving
an error message if it is not possible to use all the wires.
You should leave one blank line between each output data
line.

For example, if the input data file contained

4 3
6 20

then the output file should look approximately like

12
Too many wires