2498 - 区间

题目描述

给定 n 个闭区间 [ai,bi] 和 n 个整数 ci

你需要构造一个整数集合 Z,使得对于任意的 ∀i∈[1,n],Z 中满足 aixbi 的整数 x 不少于 ci 个。

求这样的整数集合 Z 最少包含多少个数。

输入

第一行包含整数 n

接下来 n 行,每行包含三个整数 ai,bi,ci

数据范围

1n50000, 0ai,bi50000, 1cibiai+1

输出

输出一个整数表示结果。

样例

输入

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出

6
来源

Poj1201

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 82
通过人数 58
金币数量 2 枚
难度 基础


上一题 下一题