4617 - [Wf2016]Spin Doctor

大选要到了，受候选人X的要求，你调查了n个人，并记录了每个人的3个信息： ai--他们能记忆π的多少位 bi--他们的头发数量 ci--他们是否会给候选人X投票 你需要找到某个公式使这些结果看起来有意义。你要选择2个实数S和T，将所有调查结果按aiS+biT排序。如果ci 为true的人聚集在了一起，你会觉得这个排序看起来不错。更准确地说，如果j和k分别是第一个和最后一个ci为tr ue的人的下标，你想要最小化k-j+1。注意有些S和T会让排序时出现相等的情况，这时你应该假设最坏情况发生， 即排序使得k-j+1最大。

Input

第一行一个数n(1 ≤ n ≤ 250000)为被调查的人数。 接下来每行描述一个人的ai(0 ≤ ai ≤ 2000000)、bi(0 ≤ bi ≤ 2000000)、ci ci是一个0/1变量。保证至少有一个人投了X的票（即至少有一个ci为true）

Output

对于所有可能的实数对(S,T)，输出最小的k-j+1。

Examples

Input

100
7487 4751 1
7499 5064 1
7471 5376 1
7404 5683 1
7300 5979 1
7159 6260 1
6984 6520 1
6777 6757 1
6543 6966 1
6284 7144 1
6006 7288 1
5711 7396 1
5405 7466 1
5092 7498 1
4780 7490 1
4469 7442 1
4167 7357 1
3878 7234 1
3607 7075 1
3358 6884 1
3135 6664 1
2941 6417 1
2780 6147 1
2653 5860 1
2564 5559 1
2513 5249 1
2501 4936 1
2529 4624 1
2596 4317 1
2700 4021 1
2841 3740 1
3016 3480 1
3223 3243 1
3457 3034 1
3716 2856 1
3994 2712 1
4289 2604 1
4595 2534 1
4908 2502 1
5220 2510 1
5531 2558 1
5833 2643 1
6122 2766 1
6393 2925 1
6642 3116 1
6865 3336 1
7059 3583 1
7220 3853 1
7347 4140 1
7436 4441 1
4946 8828 0
8742 4313 0
2126 2132 0
9435 3372 0
5088 584 0
278 7609 0
464 5305 0
1577 509 0
2804 8754 0
9047 1580 0
1558 5541 0
3041 9135 0
7723 9004 0
3245 7600 0
3274 8477 0
7867 5690 0
4184 9319 0
8425 475 0
942 6676 0
8254 1405 0
7168 6512 0
2541 51 0
3017 7811 0
6805 39 0
4351 8732 0
533 9472 0
1513 9570 0
634 790 0
5809 9609 0
6536 8399 0
5640 9504 0
2408 9157 0
1271 1853 0
1976 2706 0
9332 7001 0
1048 3322 0
9764 9397 0
1901 1449 0
3985 2122 0
7139 9767 0
5835 8305 0
746 585 0
3025 8187 0
2301 782 0
9741 3033 0
3960 8756 0
693 3827 0
1169 7143 0
556 8694 0
3721 1983 0

Output

61
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题