A75422.[GESP202506 七级] 调味平衡

普及/提高-

GESP

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小 A 准备了 nn 种食材用来制作料理,这些食材依次以 1,2,,n1,2,\dots,n 编号,第 ii 种食材的酸度为 aia_i,甜度为 bib_i。对于每种食材,小 A 可以选择将其放入料理,或者不放入料理。料理的酸度 AA 为放入食材的酸度之和,甜度 BB 为放入食材的甜度之和。如果料理的酸度和甜度相等,那么料理的调味是平衡的

过于清淡的料理并不好吃,因此小 A 想在满足料理调味平衡的前提下,合理选择食材,最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下,料理酸度与甜度之和的最大值吗?

输入格式

第一行,一个正整数 nn,表示食材种类数量。

接下来 nn 行,每行两个正整数 ai,bia_i,b_i,表示食材的酸度和甜度。

输出格式

输出共一行,一个整数,表示在调味平衡的前提下,料理酸度与甜度之和的最大值。

输入输出样例

  • 输入#1

    3
    1 2
    2 4
    3 2
    

    输出#1

    8
  • 输入#2

    5
    1 1
    2 3
    6 1
    8 2
    5 7
    

    输出#2

    2
    

说明/提示

数据范围

对于所有测试点,保证 1n1001 \le n \le 1001ai,bi5001 \le a_i,b_i \le 500

首页