; variables
(defun *eat-flag* nil)
(defparameter *dp* '())

(defparameter *n* 4)
(defparameter *v* '(5 4 4 9))

; functions
(defun send-int ()
  (push (parse-integer (coerce (reverse n-stack)
			       'string))
	int-list)
  (setf n-stack nil)
  )

(defun input-v (str)
  (setf n-stack '())
  (setf int-list '())
  (loop for c across str
	do
	(cond
	  ((char= c #\ )
	   (send-int)
	   )
	  (t
	    (push c n-stack)))
	finally (send-int))
  (reverse int-list)
  )

(defun input ()
  (setf *n* (read-line))
  (setf *v* (input-v (read-line)))
  )

(defun my-max (a b)
  (cond
    ((equal a nil) b)
    ((equal b nil) a)
    (t (max a b)))
  )

(defun dp-loop (l)
  (cond
    ((equal l nil) nil)
    (t
      (push (my-max (car *dp*)
		    (+ (cadr *dp*) (car l)))
	    *dp*)
      (dp-loop (cdr l)))
      )
  )

(defun n45 ()
  (input)

  (push (car *v*) *dp*)
  (push (max (car *v*) (cadr *v*)) *dp*)

  (dp-loop (cddr *v*))
  (princ (car *dp*))
  )

(n45)