必杀技选择

题目描述

你需要连续 $N$ 天消灭异世界每天诞生的一只魔物。每天你只能从两种必杀技中选择一种使用一次，并且最终两种必杀技的使用次数必须相同。已知每天两种必杀技各自需要消耗的力量，求完成 $N$ 天任务所需的最小总力量消耗。

输入格式

第一行一个整数 $N$，表示天数。接下来 $N$ 行，每行两个用空格隔开的整数 $s_1,s_2$，分别表示当天使用必杀技 $1$ 和必杀技 $2$ 需要消耗的力量。

输出格式

输出一行一个整数，表示最小的力量消耗。

样例输入

4
5 4
3 6
1 8
3 9

样例输出

14

样例解释

第一天和第二天使用必杀技 $2$，第三天和第四天使用必杀技 $1$。

数据范围

$N$ 为偶数，$2\le N\le 10^5$，$1\le s_1,s_2\le 10^6$，数据均在 int 范围内。