road

时间限制:10s      空间限制:259MB

题目描述

很久很久以前,中原地区分成了N个国家,编号为1到N,任意两个国家都可互达。每个国家有一个攻击值A[i]和防御值B[i]。定义一个人从i国去j国的危险值为:假如A[i]>B[j],则危险值为( - ),否则危险值为0。现在,Nan从国家1出发,经过每一个国家有且仅有一次,最后回到国家1,要求找出一种方案,使得其中危险值的最大值最小。


输入格式

第一行正整数N,表示有N个国家;第二行正整数A[1],A[2],x,y,z,有等式A[i]=(x*A[i-1]+y*A[i-2]+z)mod 32767;第三行正整数B[1],B[2],x,y,z,有等式B[i]=(x*B[i-1]+y*B[i-2]+z)mod 32767。


输出格式

输出一个数,表示危险值的最大值最小是多少。


样例输入

5
2 4 1231 4432 123
123 45 3245 555 6676 

样例输出

9171832
【样例说明】
A数组为2,4,13911,5151,3031 
B数据为123,45,24364,26060,21765 
其中一种最优方案为1- 2- 4- 3- 5-1,危险值分别为0,0,0,0,9171832

【数据范围】
100%  N<=1000000

提示

没有写明提示


题目来源

没有写明来源