Сізде қаладағы ең дәмді нанды пісіретін наубайхана бар. Күн сайын сіз \(n\) клиентке нан сатыласыз — олардың \(i\)-ші келушісі \(a_i\) уақытында келеді (нан пісіруді \(0\) уақытында бастауға болады). Әр клиент сіздің наубайханаға келгенде, ол өзінің сүйікті наныңызды пісіргенше күтеді және оны тікелей пештен алуға дайын. Барлығы ыстық нанды жақсы көреді, сондықтан клиент нанды күте алады, бірақ нан клиентті күтпеуі керек.

Сіздің пешіңіз бір уақытта тек бір нан пісіре алады және бұл процесс тоқтатылмайды. Әр нанды пісіруге бірдей тұрақты уақыт кетеді. Сіз барлық клиенттердің келу уақыттарын алдын ала білетіндіктен, клиенттердің күту уақытын минимизациялау үшін пісіру кестеңізді оңтайландырдыңыз.

Дегенмен, сіздің қазіргі пешіңіз ескірген, және жаңа сатып алу туралы ойланатын уақыт келді. Сіз нарықты зерттеп, \(m\) пеш түріне таңдадыңыз. Негізгі параметр — бір нанды пісіру уақыты: \(i\)-ші түр үшін бұл \(b_i\). Әрине, сіз ең жылдам пешті қалайсыз, бірақ бюджетіңіз мүмкіндік бермейтінін білмейсіз.

Салмақты шешім қабылдау үшін, сіз келесі статистиканы жинағыңыз келеді:

Әр пеш түріне оптималды пісіру кестесінде барлық клиенттердің минималды күту уақытын есептеңіз.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(m\) (\(1 \le n, m \le 200000\)) — клиенттер саны және пеш түрлерінің саны.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) (\(0 \le a_1 \le a_2 \le \ldots \le a_n \le 10^{12}\)) бар, мұнда \(a_i\) — \(i\)-ші клиенттің келу уақыты.

Үшінші жолда \(m\) бүтін сан \(b_1, b_2, \ldots, b_m\) (\(1 \le b_i \le 10^6\)) бар, мұнда \(b_i\) — \(i\)-ші пеш түрінің бір нанды пісіру уақыты.

Шығару

\(m\) жолды шығарыңыз. \(i\)-ші жолда бір сан болуы керек — егер \(i\)-ші түрдегі пешті сатып алсаңыз, клиенттердің минималды жалпы кідірісі.

Мысалдар

Енгізу 1

4 3
3 10 11 29
4 5 2

Жауап 1

4
6
1