小䓤的石头
题号：NC223457
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定 n 个从 1 到 n 编号的二元组 (a_i,b_i) 和一个大整数 k。

对不可重数集 S 定义 F_k(S) 表示将 S 的 个子集的异或和排序后的第 k 个元素。

如 ,将其所有子集的异或和排序后写出来为，那么有。


求最小的 len 使得 ，其中 表示所有 的 a_i 组成的集合。

保证 是一个合法区间。

输入描述:

第一行一个整数表示 n。

接下来 n 行，第  行两个整数为 a_i,b_i 用空格隔开。

第  行一个无前导零  串 K 代表 k-1 的二进制表示，从左往右是高位到低位。(样例解释中有体现。)

第  行一个整数s。

输出描述:

一个整数表示最小区间大小()
示例1

输入

复制 
10
16 272
8 60
1 392
24 352
16 188
1 130
8 161
24 121
24 117
24 156
111
7

输出

复制 
39

说明

读入有k=(111)_2-1=6

[117,156] 是一个合法区间，F_6(\{a_i\mid b_i\in[117,156]\})=1\leqslant 7,并且容易证明不存在 r-l<156-117=39 的合法区间，所以答案为 39 。

备注: