ZAMENA - Zamena

no tags 

Little Picsel, a long-term member of the Secret Committee, has decided to resign after years of loyal service. However, as he does not want his departure to go unnoticed, he has decided to encrypt his final suggestion for this year's Nationals, using a key only known to him. He left only a single array to the other Committee members, containing all of their IDs (the IDs are of a fixed length and need not be unique), and the statement of the problem that they must solve in order to obtain the key:

Picsel had initially traversed the array, starting from the first element towards the last, until he found an ID he liked and remembered it. Then he continued his traversal, and upon encountering a very similar ID to the one he remembered (two IDs are very similar if they differ at most in a single digit), he has two options:

  • remembering the encountered ID instead of the previously remembered one, and continuing his traversal;
  • continuing his traversal without remembering the encountered ID.

Picsel also keeps track of the total 'score' he has obtained throughout his traversal; initially, his score is set to zero, however whenever he chooses to remember a new ID, the score increases by the absolute difference of the old and new ID's digit on the position in which they differ. For example, if the previously remembered ID was 1234, and the newly remembered ID is 1274, the score increases by 4 in that case. The Committee now must determine the maximal score that Picsel could have achieved.

The Nationals have already begun, and the Committee had failed to decrypt Picsel's problem and are unable to offer the contestants a new one. As such, they asked for your help with the decryption; for additional motivation, they are offering you 100 points at the contest as a reward.

Input

The first line of the standard input contains a natural number N, representing the amount of members of the Secret Committee.

Each of the following N lines contains a single integer Ai, representing the ID of the i-th committee member in the array.

Output

Write to the first and only line of the standard output a single integer M, representing the maximal score that Picsel could have achieved.

Example

Input:
6
8823
2145
2185
3385
4145
4445 Output: 5

Explanation

Picsel first decides to remember the ID 2145. Afterwards he immediately has the option of remembering 2185 instead, however he refuses to do so, as if he were to choose to remember the ID 4145 instead, followed immediately by 4445, he would win a total score of 5:

2145 → 4145 → 4445 ⇒ score = |4 - 2| + |4 - 1| = 5

There is no strategy that will result in Picsel scoring more than five points.

Constraints

  • 1 <= N <= 105
  • 0 <= Ai < 107
  • All of the IDs Ai will be of the same length

hide comments
રચિત (Rachit): 2015-07-07 21:19:41

@problem setter, too strict timelimit IMHO.

Re (PetarV): It's not too strict, it's about 10x the time taken for the "official" solution, and allows for very reasonable constant factors.
Try using scanf instead of cin.

Last edit: 2015-07-09 03:59:23

Added by:PetarV
Date:2015-04-16
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Serbian Nationals 2015 (by Vanja Petrović Tanković)