Ledi üçün Hədiyyə

Kozak Vus uzun müddət düşündü ki, Lediyə Ad Günü üçün nə hədiyyə etsin. O, orijinal və ən əsası, faydalı bir hədiyyə etməyə qərar verdi. Buna görə də, Kozak Vus Lediyə uzunluğu $n$ olan $(a_i,b_i)$ ədədlər cütlüyü dəsti hədiyyə etdi.

Ledi əvvəlcə belə qəribə bir ədədlər dəstinə niyə ehtiyacı olduğunu anlamadı. Başlanğıc dəst Ledi üçün çox da cazibədar deyildi, buna görə də o, bu dəstin müəyyən şərtlərə cavab verən alt dəstini seçməyə qərar verdi.

Tutaq ki, Ledi başlanğıc dəstin alt dəsti olan yeni bir dəst əldə etdi. Formal olaraq, alt dəst — $(a_{i_1},b_{i_1}),(a_{i_2},b_{i_2})\dots (a_{i_m},b_{i_m})$ cütlər dəstidir, burada $0\le m\le n$ və bütün $1\le p\le m-1$ üçün $i_p<i_{p+1}$ şərti yerinə yetirilir. Qeyd edək ki, Ledi həm $0$ cüt, həm də bütün $n$ cütü seçə bilər.

Ledi hesab edir ki, əldə etdiyi dəst bütün mümkün dəstlərdən ən gözəlidir, əgər iki şərt yerinə yetirilirsə:

1. Hər kəsə məlumdur ki, Ledinin sevimli ədədi $k$-dır. Buna görə də, seçilmiş bütün $a_{i_p}$ üçün $1\le p\le m$ bitwise VƏ YA əməliyyatı $k$-dan çox olmamalıdır. 2. Bütün $b_{i_p}$ üçün $1\le p\le m$ cəmi maksimal olmalıdır.

Bitwise VƏ YA (işarə ilə $|$) — hər bir bitə tətbiq olunan əməliyyatdır, nəticədə yalnız hər iki ədədin bitləri $0$ olduqda $0$ alınır. Əks halda bit $1$ olur. Gəlin $9$ və $10$ ədədləri nümunəsində baxaq. Onların ikilik yazılışı belədir: $1001$ və $1010$, əgər $0$ olan yuxarı bitləri nəzərə almasaq. Beləliklə, VƏ YA əməliyyatı hər bir bitə tətbiq olunur. Beləliklə, sıfırıncı bit $(1|0)$ bərabərdir, bu da $1$-ə bərabərdir. Birinci bit $(0|1)$ bərabərdir, bu da $1$-ə bərabərdir. İkinci bit $(0|0)=0$ və üçüncü bit $(1|1)=1$ bərabərdir. Beləliklə, $9$ və $10$ ədədlərinin ikilik yazılışında bitwise VƏ YA $1011$-ə bərabərdir, bu da $11$-ə bərabərdir.

Ledi ən gözəl dəsti tapmaqda çətinlik çəkdi. O başa düşür ki, dəsti tapmaq çətindir, ona görə də sizdən yalnız ən gözəl dəstdəki bütün $b_{i_p}$ cəmini deməyinizi xahiş edir.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $k$ ($1\le n\le 10^6$, $0\le k<2^{30}$) ehtiva edir.

Növbəti $n$ sətirin hər biri iki tam ədəd $a_i$ və $b_i$ ($0\le a_i,b_i<2^{30}$) ehtiva edir.

Çıxış verilənləri

Bir ədəd çıxarın — seçilmiş $b_{i_p}$-lərin maksimal mümkün cəmi.

Nümunələr

Qeyd

Birinci nümunədə, əgər cavabda birinci və ikinci cütü götürsək, bitwise VƏ YA $7$-ə bərabər olacaq və axtarılan cəm $2$-ə bərabər olacaq. Cəmi artırmaq mümkün deyil, çünki bütün üç cütü götürsək, bitwise VƏ YA $k$-dan çox olan $15$-ə bərabər olacaq.

İkinci nümunədə ən sərfəlisi ikinci, üçüncü və dördüncü cütləri götürməkdir ki, cavab $6$ olsun. Əgər cavaba birinci cütü daxil etsək, onunla birlikdə yalnız üçüncü cütü götürmək olar ki, bitwise VƏ YA $k$-dan çox olmasın. Beləliklə, maksimal mümkün cəm $6$-ya bərabərdir.

Qiymətləndirmə

1. ($17$ bal): $n\le 10$; 2. ($26$ bal): $n\le 10^4$, $k<2^{10}$; 3. ($14$ bal): $k=2^t-1$, burada $0\le t\le 30$; 4. ($43$ bal): əlavə məhdudiyyətlər olmadan.