BTCODE_C - Fun With Inequalities

no tags 

You are given 'n' inequalities. Each inequality is of one of the following 4 types:
Type 1: x > v
Type 2: x < v
Type 3: x = v
Type 4: x != v

where 'x' is a variable which can only take non-negative integral values.

Your task is to find the maximum number of inequalities which are satisfied for some value of 'x'. You are also required to find the minimum value of 'x' for which the maximum number of inequalities are satisfied.

Input

The first line of input contains a single integer 'n', denoting the total number of inequalities.
Each of the next 'n' lines contain 2 space separated integers ti and vi. ti denotes the type of inequality and vi denotes the value on the right hand side of the inequality.

Output

Output two space separated integers, the first integer denoting the maximum number of inequalities which are satisfied for some value of 'x', and the second integer denoting the minimum value of 'x' for which the maximum number of inequalities are satisfied.

Example

Input:
4
1 10
2 9
3 7
4 4

Output:
3 7

Constraints:
1 <= n <= 100000
1 <= ti <= 4
1 <= vi <= 10^18

Explanation:

The given inequalities are: 1) x > 10, 2) x < 9, 3) x = 7, 4) x != 4. For x=7, the inequalities 2), 3) and 4) are satisfied.


hide comments
Raghavendran Ramachandran: 2012-09-10 15:19:27

Can a specific inequality be repeated more than once?

Gurpreet Singh: 2011-06-28 18:49:50

Last edit: 2011-06-28 19:00:32
sudipto das: 2011-03-20 05:00:07

.....

Last edit: 2011-03-20 05:19:19

Added by:suhash
Date:2011-02-26
Time limit:0.407s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India