有个盒子,对于第个盒子,如果你把它染成白色那么这个盒子的重量就是,如果你把它染成黑色重量就是,还有个限制,每个限制形如表示这两个盒子的颜色必须不同。
你想把每个盒子都染上黑色或白色,在满足所有限制的同时,使这些盒子重量的极差最小,求这个最小的极差。
第一行两个正整数
下面行每行两个正整数表示
输出一行一个整数表示最小的极差,特别的,如果无论你如何染色都无法让个限制同时满足,输出
样例输入 3 1 1 2 1 2 3 4 5 6
样例输出 3