1 \(s / 64\) \(MB / 80\) points

Little Greedy got a board for his birthday. The board has \(N\)

rows and \(M\)

columns, and has a
lowercase letter of the English alphabet in each field. During his birthday party, everyone
got bored so they decided to play a simple board game.

The game begins with placing a chip on the upper left field labeled with coordinates (1, 1).
In each turn, we must move the chip one field to the right or down, given the constraint that
it remains on the board. The game ends with moving the chip to the lower right field of the
board labeled with coordinates ( \(N\)

, \(M\)

). During the game, we take note of the array of
characters we form by moving the chip and therefore constructing a word. The goal of the
game is to find the lexicographically smallest word.

The player(s) that will suceed in constructing the lexicographically smallest word get a bag of
candy as a prize. Greedy wants to win the candy at any price, so he is asking you to write a
programme that will find the lexicographically smallest possible word.

Please note : The lexicographic order of words is the one in which the words appear in a
dictionary. If we have two words, and the words differ in the first letter, then the smaller word
is the one with the letter that comes first in the alphabet.

In test cases worth 40 points total, it will hold that, for each field, the letters located to the
right and below will be different.

The first line of input contains integers \(N\)

and \(M\)

, separated by space (1 ≤ \(N\)

, \(M\)

≤ 2000).
The following \(N\)

lines contains \(M\)

lowercase letters of the English alphabet that represent the
board.

You must output the lexicographically smallest word.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 3