Consider a dial pad of 1 to 9 digits as shown in the figure. You can not press a single digit 2 times consecutively. If you are pressing any digit, then after pressing that digit, you can only press its adjacent digit. Two digits are adjacent if they share an edge.
Cost of pressing a digit after another adjacent digit is given. Initially, you have X unit(s) of money. You need to maximize the sum of digit(s) you can press in X unit(s) of money. You can start from any digit.

Input :

• The first line of input contains an integer X, denoting amount of money you have.
• Each of the following 12 lines contains u, v and w, where w is the cost of changing digit from u to v or v to u.

Output :

• A single integer representing the maximum sum of numbers you can press in X unit of money.

Constraints :

• $1 \le X,w \le 10^{5}$
• $1 \le u ,v \le 9$