佐助题库

3266: 一起去旅行吧 题目描述 高桥要进行 N 天的旅行，第 i 天的费用为 Ai 。他还可以使用优惠券，可以免除 D 天的费用，价格为 P 。如果剩余 2 天，优惠券的作用是 3 天，那么依然可以使用。

求这 N 天旅行的最小费用。

输入

第一行有 3 个整数 N,D,P 。

第二行有 N 个整数，第 i 个为 Ai 。

1≤N≤2×10^5

1≤D≤2×10^5

1≤P≤10^9

1≤Ai≤10^9

输出

输入一行表示答案

样例输入

5 2 10

7 1 6 3 6

样例输出

20

3260: 奶牛大选

题目描述

农场一年一度的选农场主开始啦！

选举的人有 Farmer John 和 Farmer Jack，全农场有 N 个片区，第 i 个片区有 ai 只 Jack 的奶牛，bi 只 John 的奶牛，没有其他人的奶牛。

John 要在各个片区发放牧草。

如果 John 在一个区发放牧草，那么所有 John 和 Jack 的奶牛都会投票支持 John，另一方面，如果 John 不在该区发放牧草，所有 Jack 的奶牛投票支持 Jack ，而 John 的奶牛不参与投票。

求John 想赢得比 Jack 多的选票，至少要去发放牧草的片区数量 X 。

输入

第一行是一个整数 N ,

第 2 到第 N+1 行，分别是两个整数 ai,bi 。

1 ≤ N ≤ 2 × 10^5

1 ≤ ai, bi ≤ 10^9

输出

一个所求的整数 X 。

样例输入

4

2 1

2 2

5 1

1 3

样例输出

1