;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Check all patern
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; variables
(defparameter *n-m* '())
(defparameter *score* 0)
;(defparameter *scores* '())
(defparameter *scores* '(((0 1) 1)
			 ((0 2) 2)
			 ((0 3) 3)
			 ((1 2) 4)
			 ((1 3) 5)
			 ((2 3) 6)
			 ((3 2) 100)
			 ((2 1) 100)
			 ((1 0) 100))
			 )

; functions
(defun stack-to-int (nstack)
  (parse-integer (coerce (reverse nstack) 'string))
  )

(defun input-to-list (str)
  (setf nstack '())
  (setf int-list '())
  ; each character
  (loop for c across str
	do
	(cond
	  ; space
	  ((char= c #\ )
	   (push (stack-to-int nstack) int-list)
	   (setf nstack nil))
	  (t
	    (push c nstack)))
	finally (push (stack-to-int nstack) int-list)
	)
  (reverse int-list)
  )

(defun input-scores ()
  (setf l '())
  (loop repeat (cadr *n-m*)
	do
	(push (input-to-list (read-line)) l)
	)
  (setf *scores* '())
  (loop for item in l
	do
	(push (list (list (first item) (second item))
		    (third item)) *scores*))
  )

(defun input ()
  (setf *n-m* (input-to-list (read-line)))
  (input-scores)
  )

(defun permutation (xs &optional a)
  (cond ((null xs)
	 (setf *score* (max *score* (calc-score (reverse a)))))
	(t
	  (dolist (x xs)
	    (permutation (remove x xs) (cons x a)))))
  )

; (((item1 item2) score) ((item1 item2) score) ...)
; search (a b) and return score
(defun check-score (a b)
  (setf ret 0)
  (loop for item in *scores*
	do
	(if (equal (list a b) (car item))
	  (setf ret (cadr item))
	 )
	)
  ret
  )

(defun calc-score (l)
  (setf ret 0)
  (setf ary (make-array (length l)
			:initial-contents l))
  (loop for item across ary
	for i from 0 to (1- (length ary))
	do
	(loop for j from (1+ i) to (1- (length ary))
	      do
	      (setf ret (+ ret (check-score item (aref ary j))))
	      )
	)
  ret
  )

(defun n90 ()
  (input)

  ; make list from n
  (setf l '())
  (loop for i from 0 to (1- (car *n-m*))
	do
	(push i l)
	)

  ; all permutation
  (permutation l)
  (princ *score*)
  )

(n90)