The Reliquary Barge of Lake Senmarrow

The drowned chapels on the far shore of Lake Senmarrow are to be resealed, and the Wardens of Senmarrow need their sacred reliquaries carried across. The Wardens have commissioned the barge and want it built light. A barge rated for more weight costs more to build. The guild must therefore name the lowest weight rating that still gets the job done.

The reliquaries stand on the quay in a fixed row, and the rules of the crossing are strict:

• The reliquaries must be loaded in the order they stand. Each crossing carries a contiguous run of the next reliquaries still on the quay.
• A reliquary is never split between crossings.
• The total weight carried on one crossing must not exceed the barge's limit. Exactly equal to the limit is allowed.
• All reliquaries must be across in at most trips crossings. Using fewer crossings is fine.

Write minBargeLimit(weights, trips).

• weights is a list of positive integers: the reliquaries' weights, in quay order. It may be empty.
• trips is a positive integer (at least 1): the most crossings allowed.

Return the smallest integer weight limit under which every reliquary can be carried across within trips crossings. If weights is empty, return 0.