#P1746. 2024.03.24-aliyun-第一题-塔子哥的彩灯节

2024.03.24-aliyun-第一题-塔子哥的彩灯节

问题描述

塔子哥的家乡即将举行一年一度的彩灯节。节日中，塔子哥负责布置一排彩灯，每个彩灯可以选择亮起“红”或“绿”两种颜色，用红色代表喜庆，会增加喜气值；用绿色代表和谐，会增加安宁值。但是为了避免颜色单调，相邻的灯不能亮起相同的颜色。在确保相邻彩灯颜色不同的前提下，塔子哥想知道如何点亮这些彩灯才能使得喜气值和安宁值的总和最大。

输入格式

第一行包含一个正整数 nn，表示彩灯的总数。

接下来 nn 行，每行两个正整数 rir_i 和 gig_i，分别表示第 ii 个彩灯亮起红色和绿色时所增加的喜气值和安宁值。

输出格式

输出一行一个整数，表示塔子哥点亮彩灯后能获得的最大总和值。

样例输入

4
1 3
4 3
5 6
2 3

样例输出

15

评测数据与规模

  • 1≤n≤1051 \leq n \leq 10 ^ 5，1≤ri,gi≤1091 \leq r_i, g_i \leq 10 ^ 9。

知识点:*****

查看知识点以及同类型题目

Statistics