During the loading of the game "Dungeons and Candies" you are required to get descriptions of k levels from the server. Each description is a map of an n × m checkered rectangular field. Some cells of the field contain candies (each cell has at most one candy). An empty cell is denoted as " . " on the map, but if a cell has a candy, it is denoted as a letter of the English alphabet. A level may contain identical candies, in this case the letters in the corresponding cells of the map will be the same. When you transmit information via a network, you want to minimize traffic — the total size of the transferred data. The levels can be transmitted in any order. There are two ways to transmit the current level A : You can transmit the whole level A . Then you need to transmit n · m bytes via the network. You can transmit the difference between level A and some previously transmitted level B (if it exists); this operation requires to transmit d A , B · w bytes, where d A , B is the number of cells of the field that are different for A and B , and w is a constant. Note, that you should compare only the corresponding cells of levels A and B to calculate d A , B . You cannot transform the maps of levels, i.e. rotate or shift them relatively to each other. Your task is to find a way to transfer all the k levels and minimize the traffic. The first line contains four integers n , m , k , w (1 ≤ n , m ≤ 10; 1 ≤ k , w ≤ 1000) . Then follows the description of k levels. Each level is described by n lines, each line contains m characters. Each character is either a letter of the English alphabet or a dot (" . "). Please note that the case of the letters matters. In the first line print the required minimum number of transferred bytes. Then print k pairs of integers x 1 , y 1 , x 2 , y 2 , ..., x k , y k , describing the way to transfer levels. Pair x i , y i means that level x i needs to be transferred by way y i . If y i equals 0, that means that the level must be transf