#lang scheme

#|
Problem 8: River Crossing 

Farmer John is herding his N cows (1 <= N <= 2,500) across the
expanses of his farm when he finds himself blocked by a river.
A single raft is available for transportation.

FJ knows that he must ride on the raft for all crossings and that
that adding cows to the raft makes it traverse the river more slowly.

When FJ is on the raft alone, it can cross the river in M minutes
(1 <= M <= 1000).  When the i cows are added, it takes M_i minutes
(1 <= M_i <= 1000) longer to cross the river than with i-1 cows
(i.e., total M+M_1 minutes with one cow, M+M_1+M_2 with two, etc.).
Determine the minimum time it takes for Farmer John to get all of
the cows across the river (including time returning to get more
cows).

PROBLEM NAME: river

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: M_i

SAMPLE INPUT (file river.in):

5 10
3
4
6
100
1

INPUT DETAILS:

There are five cows. Farmer John takes 10 minutes to cross the river
alone, 13 with one cow, 17 with two cows, 23 with three, 123 with
four, and 124 with all five.

OUTPUT FORMAT:

* Line 1: The minimum time it takes for Farmer John to get all of the
        cows across the river.

SAMPLE OUTPUT (file river.out):

50
|#

(require (planet "memoize.ss" ("dherman" "memoize.plt" 2 1)))


;; river-crossing: number (listof number) -> number
;; Returns the minimal amount of time necessary to bring the cows home.
;;
;; example: (river-crossing 10 '(3 4 6 100 1))  expected to be 50.
;;
(define (river-crossing john-time cow-times)
  (local (;; crossing-with-cows: number -> number
          ;; Computes the cost of carrying n cows across the river.
          (define crossing-with-cows
            (memo-lambda* (n)
              (cond
                [(= n 0)
                 0]
                [else
                 (find-minimal-solution (try-crossing-with-k-cows 1 n)
                                        2
                                        n)])))
          
          ;; find-minimal-solution: number number number -> number
          ;; Looks for a minimal solution by using
          ;; try-crossing-with-k-cows between k and n, inclusive.
          (define (find-minimal-solution best-solution-so-far k n)
            (cond
              [(> k n)
               best-solution-so-far]
              [else
               (find-minimal-solution (min best-solution-so-far
                                           (try-crossing-with-k-cows k n))
                                      (add1 k)
                                      n)]))
          
          ;; try-crossing-with-k-cows: number number -> number
          ;; Computes the minimal cost of crossing n cows, if we try
          ;; with k cows going across first.
          (define (try-crossing-with-k-cows k n)
            (+ (carrying-cows-with-john k)
               (going-back-for-the-others (- n k))))
          
          ;; carrying-cows-with-john: number -> number
          ;; The cost of carrying n cows along with john across
          ;; the river.
          (define carrying-cows-with-john
            (memo-lambda* (n)
              (cond
                [(= n 0)
                 john-time]
                [else
                 (+ (carrying-cows-with-john (sub1 n))
                    (list-ref cow-times (sub1 n)))])))
          
          ;; going-back-for-the-others: number -> number
          ;; Computes the cost of moving n cows, when john is on the other
          ;; side of the river and may have to go back for the n others.
          (define (going-back-for-the-others n)
            (cond
              [(= n 0)
               0]
              [else
               (+ john-time (crossing-with-cows n))])))
    
    (crossing-with-cows (length cow-times))))


;; Small driver program.
(define (main)
  (let* ([number-of-cows (read)]
         [farmer-john-time (read)]
         [cow-times (build-list number-of-cows (lambda (i) (read)))])
    (display (river-crossing farmer-john-time cow-times))
    (newline)))