Advance Catering Map

Paul owns a catering company with \(k\) catering teams, each equipped with a set of catering equipment. Every week the company receives \(n\) requests for events, and each request must be serviced by sending a team with its equipment. When a team is used for its first event, the equipment is moved from the company depot to the event location at some cost. If a team has to service more than one event in the same week, then after finishing an event the team must move the equipment from the previous event's location directly to the next event's location, incurring a given moving cost.

It is always possible to transport the equipment from the location of a request to the location of any later request. In weeks when \(k < n\), some teams may be assigned to more than one event. Paul wants to create an Advance Catering Map to service all the events while minimizing the total cost of moving equipment. The total cost is computed as follows: if an event is the first event of a team then the cost is \(C_{0,i}\) (the cost from the depot to event \(i\)); if a team services consecutive events \(i\) and \(j\) (with \(i<j\)) then the cost incurred is \(C_{i,j}\).

Under the assumption that the events are sorted in ascending order by their scheduled times, and moreover if we assume that an optimal solution exists in which each team is assigned a contiguous block of events, the problem is reduced to partitioning the sequence of events into at most \(k\) contiguous segments. For a segment covering events \(i\) through \(j\), the cost is:

[ \text{cost}(i,j)= C_{0,i} + \sum_{t=i}^{j-1} C_{t,t+1} ]

Your task is to compute the minimal total moving cost needed to cover all \(n\) events using at most \(k\) teams (note that using fewer teams is allowed).

inputFormat

The input is given in three lines:

1. The first line contains two integers \(k\) and \(n\) separated by a space, where \(k\) is the number of available teams and \(n\) is the number of events.
2. The second line contains \(n\) integers. The \(i\)th integer denotes \(C_{0,i}\), the cost to move equipment from the company depot to event \(i\).
3. The third line contains \(n-1\) integers. The \(i\)th integer denotes \(C_{i,i+1}\), the cost to move equipment directly from event \(i\) to event \(i+1\).

You may assume that the events are given in chronological order.

outputFormat

Output a single integer representing the minimal total moving cost required to service all events.

sample

2 3
5 2 4
3 1

8