a129. TOI 2025/04 潛力組：水管

題目描述

兩側各有 N 個依序排列的接口，一側是出水口，另一側是進水口，各自有最大流量。可以用水管將一個出水口與一個進水口連接，每個接口最多使用一次，也可以不用。水管的流量是兩端最大流量的較小值。

水管不能交錯：若兩條水管分別連接第 i、j 個出水口與第 p、q 個進水口，且 i<j，就必須有 p<q。請求出所有水管流量總和的最大值。

輸入格式

第一行為 N；第二行有 N 個出水口流量 aᵢ，第三行有 N 個進水口流量 bᵢ，皆按排列順序給出。

• 2 ≤ N ≤ 2000
• 1 ≤ aᵢ、bᵢ ≤ 1000000

輸出格式

輸出可達成的最大總流量。

來源

TOI 2025 年 4 月潛力組〈水管〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202504/Pipe.pdf