The Penguin-Avia airline, along with other Antarctic airlines, experiences
financial difficulties because of the world's economic crisis. People of
Antarctica economize on flights and use trains or prefer to stay at home.
The airline's management hopes that the number of their clients will increase
in the summer due to the tourists visiting the coastal resorts. In order to
hold out till the summer, it was decided to optimize the flight scheme by
cancelling some flights and introducing some new flights.
Director of Penguin-Avia assumes that after the optimization the flight scheme
must have the following properties:
- Using one or more Penguin-Avia flights, one can get from any Antarctic airport to any
- The scheme must contain the minimal number of flights among all the schemes
satisfying the first property.
However, not everything is that easy in Antarctica. For cancelling a flight,
the airline must pay a one-time forfeit of d
Antarctic dollars. To
obtain slots for a new flight, the company must spend a
dollars to grease the palm of the godfather of the Antarctic mafia nicknamed Walrus.
Help Director of Penguin-Avia transform the existing flight scheme spending as
little money as possible. For doing that, you will be presented with a travel card
for all flights of the airline.
In the first line you are given the number n of airports in Antarctica, 2 ≤ n ≤ 100.
In the second line you are given the integers d and a, 1 ≤ d, a ≤ 106.
The following n lines describe the existing scheme of Penguin-Avia
flights in the form of an n × n matrix. There is “1” in a cell (i,
j) of the matrix if the airline has flights between the airports i and j.
Otherwise, there is “0” in the cell. It is guaranteed that the matrix is symmetric
and there are only zeros on its diagonal.
In the first line output the minimal amount of money necessary for the
optimization of the existing flight scheme. In the next n lines give the
plan of changing the scheme in the form of an n × n matrix.
A cell (i, j) of this matrix contains the symbol
“d” if the flights between the airports i and j
should be cancelled. In the case when a new flight should be introduced between
these airports, the cell contains the symbol “a”. The remaining
cells contain the symbol “0”. The matrix must be symmetric.
If there are several optimal schemes, output any one of them.
Problem Author: Alexander Ipatov
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009