#¨. [CSP模拟]造船

    Type: Default 1000ms 256MiB

[CSP模拟]造船

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Y想要在虚拟世界里造船。最开始 nn 个船的完成度全部都为 00 。小Y第 ii 时刻可以在 aia_{i}bib_{i} 两艘船中选择一艘让这艘船的完成度 +1+1

由于国家政府是奇数控,所以所有偶数完成度的船只都将被摧毁,小Y想知道 mm 时刻后能剩下来的船只最多有多少艘。

输入格式

第一行两个整数 nnmm

接下来 mm 行,每行两个整数 aia_{i} , bib_{i}

样例

input

8 6
1 2
3 4
4 5
6 7
7 8
8 6

output

6

数据范围与提示

20%的数据,m20,n100m≤20,n≤100

20%的数据,n20,m100n≤20,m≤100

20%的数据,n100,m<=500n≤100,m<=500

对于100%的数据,1n,m2000001≤n,m≤200000

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45