Description
Many of you may have played a card game called "Card Erasing". Such type of game have different variations and one is available on the Little Game Center of www.xiaonei.com.
Generally, in such games, a player can get points by eliminating cards from a certain bulk. For simplicity, let us use integer 1 to 13 to represent cards Ace, Two, … , Queen and King. Starting at a base card with integer number X, one can eliminate a card that is adjacent to the base card, which means the number of that card should be X-1 or X+1. In addition, King and Ace are considered to be adjacent with each other. After eliminating a card, this card will replace the base card in the next turn. Now Facer is quite interested in one such card game and he wants to maximize his points. He told the rules of this game to Dzx and now our great Dzx is asking you to help him. There are n×(n+1)/2 cards to be eliminated, arranging in the order as below:
Only the cards that have not been covered can be took away. So at first only cards on the last row satisfied such condition. If more than one card can be eliminated at a time, the player can choose any one. The player has m chances to refresh the base card, replacing it by a randomly generated card. The player can refresh the base card at any time, for example, when no move can be made. The game is over when all cards have been eliminated, or no move can be made and there are no more chances to refresh cards. Each time a player eliminates a card, he gets P points, but the player losts Q points if he refresh the base card. Thus the total points the player got may be negative. To make this game even easier, let us suppose all n×(n+1)/2 cards are known before eliminating them. You are given the starting state of this game, please determine the maximum expectation of the points Facer could get.
Input
The input contains several test cases.
For each test case, two integers n, m are iven in the first line.
The second line contains n×(n+1)/2 numbers depicting the bulk of cards. The cards are given from top to bottom, and from left to right when they are in the same row. The last line of each test case are the integers P, Q, and X, where X represents the initial base card. The input file ends with two zeroes. (1≤n≤5, 0≤m≤100, 0≤P, Q≤100)
Output
For each test case, print the maximum expectation of points in a separate line, rounded to the second digit after the decimal point.
Sample Input
2 1
10 1 2
100 0 7
0 0
Sample Output
61.54
Hint
The sample has three cards and only one chance to refresh base card.
At first only the cards on the last row, 1 and 2 can be eliminated. As the base card is 7, no move can be made without refreshing the base card.
If the base card becomes 13, 1, 2 or 3 after refreshing, Facer can took away the two cards on the last row, getting 200 points and then the game is over. Otherwise the game will be over with 0 points.
So the expectation is 200*(4/13) + 0*(9/13).
