آنتن (Antenna)

شهر آنتن‌سیتی سرزمین گربه‌هاست. این شهر شامل $n$ آنتن است که در یک ردیف از چپ به راست با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند که روی هرکدام از آن‌ها یک گربه‌ی نگهبان در حال نظارت به شهر است. قدرت آنتن $i$اُم برابر $c_i$ است که روی آن گربه‌ای با قدرت $a_i$ قرار دارد. رنگ‌بندی آنتن‌ها از چپ به راست در ابتدا به صورت $m$ بلوک متوالی با رنگ‌های متفاوت است که بلوک $i$اُم به طول $b_i$ است؛ به عنوان مثال اگر $b = \langle 3,2,4 \rangle$ باشد و رنگ آنتن‌های بلوک $i$اُم برابر با $i$ باشد، رنگ آنتن‌ها به ترتیب برابر با $\langle 1, 1, 1, 2, 2, 3, 3, 3, 3 \rangle$ است.

میو‌ و میا از اعضای شهر آنتن‌سیتی، حوصله‌شان سر رفته و می‌خواهند خودشان را سرگرم کنند. به دلیل قدرت عجیب میو و میا، آن‌ها می‌توانند طول بلوک‌ها را باهم جابجا کنند؛ به عنوان مثال آن‌ها می‌توانند ترتیب اولیه‌ی $\langle 3, 2, 4 \rangle$ که نشان‌دهنده‌ی $\langle 1, 1, 1, 2, 2, 3, 3, 3, 3 \rangle$ است را به $\langle 2, 4, 3 \rangle$ که برابر با $\langle 1, 1, 2, 2, 2, 2, 3, 3, 3 \rangle$ است تغییر دهند.

میو و میا می‌خواهند با هم میوسیم بازی کنند. روند بازی به شکل زیر است:

در ابتدا آن‌ها ترتیب بلوک‌ها را به صورت دلخواه تغییر می‌دهند و آنتن‌ها را با رنگ جدیدشان رنگ‌آمیزی می‌کنند.
سپس سه عدد مختلف $1 \leq i < k < j \leq n$ را به گونه‌ای که رنگ آنتن $i$اُم و $j$اُم متفاوت باشد انتخاب می‌کنند.
در انتها آن‌ها به اندازه‌ی $(a_i \oplus a_j) + c_k$ کیلو غذای گربه‌ دریافت می‌کنند!

بیش‌ترین مقداری که آن‌ها می‌توانند از بازی میوسیم غذای گربه دریافت کنند چقدر است؟ به آن‌ها کمک کنید تا پاسخ این سوال را در $t$ حالت اولیه‌ی مختلف که اطلاعات مربوط به هرکدام از آن‌ها به شما داده می‌شود را پیدا کنید.

ورودی

خط اول ورودی شامل عدد $t$ است که نشان‌دهنده‌ی تعداد ورودی‌های مختلف است. سپس برای هرکدام از $t$ ورودی پیش‌رو:

خط اول شامل دو عدد $n$ و $m$ است که نشان‌دهنده‌ی تعداد آنتن‌های شهر و رنگ‌های مختلف آن‌هاست.
خط دوم شامل $n$ عدد است که با فاصله از هم جدا شده‌اند و عدد $i$اُم نشان دهنده‌ی مقدار $a_i$ است.
خط سوم شامل $m$ عدد است که با فاصله از هم جدا شده‌اند و عدد $i$اُم نشان‌دهنده‌ی مقدار $b_i$ است.
خط چهارم شامل $n$ عدد است که با فاصله از هم جدا شده‌اند و عدد $i$اُم نشان‌دهنده‌ی $c_i$ است.

خروجی

خروجی شامل $t$ خط است. در خط $i$اُم خروجی باید حداکثر میزان جایزه‌ای که میو و میا می‌توانند در میوسیم بازی داخل ورودی $i$اُم بگیرند را خروجی دهید.

زیرمسئله‌ها

زیرمسئله اول (۳ نمره): $t=1, n \leq 7, m \leq 7$
زیرمسئله دوم (۱۵ نمره): مجموع $n$ در $t$ ورودی مختلف حداکثر برابر با $500$ است
زیرمسئله سوم (۷ نمره): مجموع $n$ در $t$ ورودی مختلف حداکثر برابر با $5000$ است
زیرمسئله چهارم (۳۲ نمره): $m \leq 500, c_i=1$
زیرمسئله پنجم (۲۵ نمره): $b_i=1$
زیرمسئله ششم (۱۸ نمره): بدون محدودیت اضافی

محدودیت‌ها

$1 \leq t \leq 2 \times 10^5$
$3 \leq n \leq 2 \times 10^5$
$2 \leq m \leq n$
$0 \leq a_i, c_i \leq 2 \times 10^5$
$1 \leq b_i \leq n$
$b_1 + b_2 + … + b_m = n$
مجموع $n$ در $t$ ورودی مختلف حداکثر برابر با $2 \times 10^5$ است.

ورودی و خروجی نمونه

ورودی نمونه	خروجی نمونه
2 5 2 1 2 3 4 5 3 2 5 4 3 2 1 4 2 7 1 4 6 2 2 3 3 3 3	10 10

شرح ورودی و خروجی نمونه

در ورودی اول با حفظ رنگ آنتن‌ها، حداکثر مقدار جایزه در حالت $i=2,j=5,k=3$ است: $$(a_2 \oplus a_5) + c_3 = (2 \oplus 5) + 3 = 7 + 3 = 10$$

همچنین با تغییر رنگ آنتن‌ها به $\langle 1, 1, 2, 2, 2 \rangle$، حداکثر مقدار جایزه در حالت $i=2,j=5,k=3$ است: $$(a_2 \oplus a_5) + c_3 = 10$$

در ورودی دوم با حفظ رنگ آنتن‌ها، حداکثر مقدار جایزه در حالت $i=2,j=4,k=3$ است: $$(a_2 \oplus a_4) + c_3 = (1 \oplus 6) + 3 = 7 + 3 = 10$$