題目描述

部門在進行需求開發時需要進行人力安排。

當前部門需要完成 N 個需求，需求用 requirements 表述，requirements[i] 表示第 i 個需求的工作量大小，單位：人月。

這部分需求需要在 M 個月內完成開發，進行人力安排后每個月人力時固定的。

目前要求每個月最多有2個需求開發，并且每個月需要完成的需求不能超過部門人力。

請幫助部門評估在滿足需求開發進度的情況下，每個月需要的最小人力是多少？

輸入描述

輸入為 M 和 requirements，M 表示需求開發時間要求，requirements 表示每個需求工作量大小，N 為 requirements長度，

• 1 ≤ N/2 ≤ M ≤ N ≤ 10000
• 1 ≤ requirements[i] ≤ 10^9

輸出描述

對于每一組測試數據，輸出部門需要人力需求，行末無多余的空格

用例

輸入	3 3 5 3 4
輸出	6