题解

题目描述

某公司有 $2$ 个仓库（用 $A$ 和 $B$ 表示），需要给 $m$（$m$ 为偶数）个营业网点各配送一件货物。假设每个仓库正好都有 $\tfrac{m}{2}$ 件货物，配送给不同营业网点的费用使用一个二维数组 $\mathit{cost}$ 表示，其中

表示第 $i$ 个营业网点从 $A$ 仓发货的运费为 $A_i$，从 $B$ 仓库发货的费用为 $B_i$。请计算 $m$ 件货物配送的最低费用，要求每个营业网点都有一件货物送到。

题目内容

某公司有 $2$ 个仓库(用 $A$ 和 $B$ 表示)，需要给 $m$ ( $m$ 为偶数)个营业网点各配送一件货物。假设每个仓库正好都有 $m/2$ 件货物，配送给不同营业网点的费用使用一个二维数组 $cost$ 表示，其中 $cost[i]=[Ai,Bi]$，表示第 $i$ 个营业网点从 $A$ 仓发货的运费为 $Ai$ ，从 $B$ 仓库发货的费用为 $Bi$ 。请计算 $m$ 件货物配送的最低费用，要求每个营业网点都有一件货物送到。

输入描述

第一行是一个整数 $M$ ，代表营业网点数量。$2<M<=100$， $M$ 为偶数第二行是一个长度为 $M$ 的二维数组 $cost$ ，其中 $cost[i]=[Ai,Bi]$，$Ai$ 和 $Bi$ 分别表示从 $A、B$ 仓库发货的费用。

$1<=Ai，Bi<=1000$

输出描述

一个整数，表示最低费用

样例1

输入

2
[[10,30],[30,200]]

输出

60

说明

$2$ 个营业网点，每个仓库备有 $1$ 件货物

第 $1$ 个营业网点从 $B$ 发货，费用 $30$

第 $2$ 个营业网点从 $A$ 发货，费用 $30$

样例2

输入

4
[[10,30],[30,200],[300,50],[40,20]]

输出

110

说明

$4$个营业网点，每个仓库有$2$件货物

第 $1$ 个营业网点从 $A$ 发货，费用 $10$

第 $2$ 个营业网点从 $A$ 发货，费用 $30$

第 $3$ 个营业网点从 $B$ 发货，费用 $50$

第 $4$ 个营业网点从 $B$ 发货，费用 $20$