JSOI 王国里有 N 个机场,编号为 1 到 N。从 i 号机场到 j 号机场需要飞行 $T{i,j} 的时间。由于风向,地理位置和航空管制的因素,T{i,j} 和 T_{j,i}$ 并不一定相同。
此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 k 号机场时,需要花费 P_k 的维护时间才能再次起飞。
JS Airways 一共运营 M 条航线,其中第 i 条直飞航线需要在 D_i 时刻从 X_i 机场起飞,不经停,飞往 Y_i 机场。
为了简化问题,我们假设 JS Airway 可以在 0 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。
JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 M 个航班。