;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Implement input system
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; variables
(defparameter tmp-score 0)
(defparameter *now-score* 0)
(defparameter *items* '(0))
(defparameter *n-m* '(4 9))
(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)
  )

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

; val=3 index=1 pre-l=(0 2 1)
; calc the score of (0 3 2 1)
(defun check-score (val index pre-l)
  (setf x (make-array (length pre-l)
		      :fill-pointer 0))
  (setf ret 0)
  ; Calc the score at this index
  (loop for item in pre-l
	for i from 0 to (1- (length pre-l))
	do
	(cond
	  ((< i index)
	   (vector-push (get-score item val) x)
	   )
	  (t 
	    (vector-push (get-score val item) x)
	    )
	  )
	)
  (loop for i across x
	summing i into total
	finally (setf ret total))
  ret
  )

; (set-items 0 2 '(0 1))
; $ (2 0 1)
; (set-items 1 2 '(0 1))
; $ (0 2 1)
(defun set-items (index val l)
  (cond
    ((= index 0)
     (setf l (concatenate 'list (list val) l)))
    (t
      (push val (cdr (nthcdr (1- index) l))))
    )
  l
  )

; return the permutated array
; and the highest score on the items
(defun search-pos (val l pre-score)
  (setf tmp-score '0)
  (setf insert-index '0)
  ; compare val to each element in l
  (loop for i from 0 to val
	do
	(cond ((< tmp-score (check-score val i l))
	       (setf tmp-score (check-score val i l))
	       (setf insert-index i)
	       )
	      )
	)

  ; update list
  (setf *items* (set-items insert-index val l))
  (setf *now-score* (+ tmp-score pre-score))
  )

; Calculate the highest score among given items
(defun calc-score (n)
  (loop for i from 1 to (1- n)
	do
	(search-pos i *items* *now-score*)
	)
  )

(defun n90 ()
  (input)
  (calc-score (car *n-m*))
  (princ *now-score*)
  )

(n90)