等值拉面

等值拉面

测试数据来自 system/1222

背景

每天中午的下课铃一响,浙江镇海中学的同学们都会冲出学校来附近的小饭馆吃饭,刹那间天昏地暗,飞砂走石,家家餐馆内都是一片黑压压的人 。馄饨店、饺子馆,在学校附近开一家红一家。身为镇海中学信息中心首席科学顾问兼资深信息学竞赛辅导老师Dennis看到了,他为了在业余时间方便学生,他租了学校附近的一家店面,雇了几个拉面师傅,开了一家“正宗兰州牛肉拉面馆”,生意还不错。

描述

话说Dennis的拉面馆隆重开张后,由于厨师手艺还未达到炉火纯青的地步,每碗拉面的重量并不都全部相等,故Dennis每天需亲自出马调节。

不过Dennis的拉面十分特殊,每碗都分成上下两部分,每部分的拉面重量均在1至6之间,且是整数,例如:现有排成行的4碗拉面
第一碗,上部分拉面重量为6,下部分拉面重量为1;
第二碗,上部分拉面重量为1,下部分拉面重量为5;
第三碗,上部分拉面重量为1,下部分拉面重量为3;
第四碗,上部分拉面重量为1,下部分拉面重量为2;
所有拉面上部分的重量之和为sum-up=6+1+1+1=9,下部分的数量之和为sum-down=1+5+3+2=11。这4碗拉面的上下数量之差的绝对值为11-9=2。

但是Dennis的每碗拉面上下可以互换,但只限于同一碗拉面,交换一次成为一次操作。请你帮助Dennis用最少的操作次数使给出的n份拉面的上下数量之差的绝对值最小。

例如这以上的4碗拉面,只需将第四碗拉面的上下部分交换,便可使上下部分之差为0。

格式

输入格式

第一行是一个正整数n (1≤n≤1000),表示拉面的碗数。

接下来的n行表示n碗拉面的详细情况。

每行有两个用空格隔开的正整数,分别表示每碗拉面上下部分的数量a和b(1≤a,b≤6)。

输出格式

输出一个整数。表示求得的最小操作数。

样例1

样例输入1

4
6 1
1 5
1 3
1 2

样例输出1

1

限制

共10点,每点1秒。

提示

30%的数据,n<=15
100%的数据,n<=1000

来源

fangyuhua&ycglovewxx

信息

ID
1335
难度
(无)
分类
动态规划 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者