#P10756. 球王的困惑

    ID: 9874 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-不变量分析支配关系交换论证向下取整与向上取整

球王的困惑

题目描述

一场足球比赛没有平局,获胜方得 33 分,失败方得 00 分。现在已知各队当前积分,每支队伍还需要参加恰好两场比赛。

剩余赛程和胜负可以任意安排,但一支队伍不能与自己比赛。同一对不同的队伍可以交手多次。

给定小 Y 所在队伍的当前积分和其他队伍的积分分布,求小 Y 所在队伍最终能取得的最高名次。名次等于最终积分严格高于该队的队伍数量加 11,同分的队伍不排在它之前。

输入格式

第一行两个正整数 t,scoret,\mathrm{score}。score\mathrm{score} 表示小 Y 所在队伍的当前积分。

接下来 tt 行,每行两个正整数 si,numis_i,\mathrm{num}_i,表示除小 Y 所在队伍外,恰有 numi\mathrm{num}_i 支队伍当前积分为 sis_i。

输出格式

输出一行一个正整数,表示可能取得的最高名次。

样例 1

1 1
7 2
2

样例 2

2 1
7 1
2 1
1

样例 3

8 11
5 2
12 4
17 8
19 2
99 1
13 3
15 25
14 3
18

数据范围

  • 20%20\% 的数据满足 ∑inumi≤5\sum_i\mathrm{num}_i\le5。
  • 40%40\% 的数据满足 t≤50t\le50。
  • 所有数据满足 1≤t≤1051\le t\le10^5,0<score,si,numi≤1090<\mathrm{score},s_i,\mathrm{num}_i\le10^9,且 sis_i 互不相同。

原 PDF 题面