编程介的小学生
2017-08-18 05:40
采纳率: 17.1%
浏览 602
已采纳

magic balls

Problem Description
The town of W has N people. Each person takes two magic balls A and B every day. Each ball has the volume ai and bi. People often stand together. The wizard will find the longest increasing subsequence in the ball A. The wizard has M energy. Each point of energy can change the two balls’ volume.(swap(ai,bi)).The wizard wants to know how to make the longest increasing subsequence and the energy is not negative in last. In order to simplify the problem, you only need to output how long the longest increasing subsequence is.

Input
The first line contains a single integer T(1≤T≤20)(the data for N>100 less than 6 cases), indicating the number of test cases.
Each test case begins with two integer N(1≤N≤1000) and M(0≤M≤1000),indicating the number of people and the number of the wizard’s energy. Next N lines contains two integer ai and bi(1≤ai,bi≤109),indicating the balls’ volume.

Output
For each case, output an integer means how long the longest increasing subsequence is.

Sample Input
2
5 3
5 1
4 2
3 1
2 4
3 1
5 4
5 1
4 2
3 1
2 4
3 1

Sample Output
4
4

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

  • threenewbee 2017-08-18 15:41
    最佳回答
    评论
    解决 无用
    打赏 举报
查看更多回答(1条)

相关推荐 更多相似问题