URI Online Judge | 2017

Six Strings

By Syed Sarfaraz Akhtar, International Institute of Information Technology Hyderabad IN India

Timelimit: 5

The problem is simple. Given a string(x) and 5 other strings, find the string with the least edit distance with x.

If the value of this edit distance is greater than k, print -1.

Input

The first line contains the string x ( 1 ≤ len(x) ). The next line contains an integer k ( 1 ≤ k ≤ 100 ). Each one of the next 5 lines contain a string y ( len(y) ≤ 100000).

Output

Print the index of the closest string on the first line. If this value was not equal to -1, so print the value of the edit distance on the second line.

Input Sample Output Sample

cbufllatkz

5

cbofllafkz

cbhflluteq

cbuzqzatmz

msrzlxaekz

xbufpltpkl

1

2