sequence of N (1 <= N <= 200) books on a bookshelf contains respectively s_1, s_2, ..., s_N pages (1 <= s_i <= 10,000,000). These books must be digitized by K employees (1 <= K <= 100). The first employee will process 0 or more of the books starting at s1; the second employee will process 0 or more of the next books in sequence and so on. Each employee is paid d_1 dollars per page for her first processed book, d_2 dollars per page for her second processed book, ..., d_i dollars per page (0 <= d_i <= 10,000,000) for her i-th processed book. Write a program to determine the minimum possible cost to process all the books.

* Line 1: Two space-separated integers, N and K * Line 2: N space-separated integers, respectively s1, s2, ..., sN * Line 3: N space-separated integers, respectively d1, d2, ..., dN

* Line 1: A single line on the standard output, the minimal cost the employer has to pay to process all the books.

USAICO 2005 Day 3