beautiful-badges

Lucy has got the task to create badges for all students of the school. A badge is created by superimposing two squares. The bottom square should be of blue colour and top square should be of yellow colour. The squares must be rotated in such a way that the projection of the badge displays 8 distinguishable vertices.

Please help Lucy find out the maximum number of badges she can make with available n squares. 

Input Format:
The first line of input file contains integer n.
Each of the next n lines contain two space separated integers, ci and di. ci is the colour number and di is the length of side of square

Output Format:
Print the maximum number of badges that can be made.

Constraints:
1 ≤ n ≤ 100000
1 ≤ di ≤ 1000
1 ≤ ci ≤ 2 

Notes:
- ci = 1 denotes blue color and vice-versa.

Problem Statement in native Language: http://hck.re/xepWPj

SAMPLE INPUT
10
1 3
1 17
2 13
2 13
2 6
1 10
2 8
1 7
1 8
2 8

SAMPLE OUTPUT
4

Source: hackerearth | Difficulty: HARD
Tags: Graph algorithms

Flows and cuts


Solutions: