Время раскладывать камни
На столе в ряд расположено N ящиков, каждый из которых либо пуст, либо содержит несколько камней. За один ход можно сделать одно из следующих действий:
взять один камень из крайнего ящика и переложить в соседний,
взять два камня из «некрайнего» ящика и положить их по одному в соседние с ним ящики.
Требуется определить, можно ли достичь таким образом определенного расположения камней в ящиках, и, если можно, вычислить минимальное количество ходов, которое для этого требуется.
Входные данные
В первой строке одно натуральное число N – количество ящиков, 2 ≤ N ≤ 20.
Во второй строке N целых неотрицательных чисел a_i через пробел, где a_i – исходное количество камней в i-ом ящике, 0 ≤ a_i ≤ 100. Сумма всех a_i не больше 100.
В третьей строке N целых неотрицательных чисел b_i через пробел, где b_i – желаемое количество камней в i-ом ящике, 0 ≤ b_i ≤ 100.
Выходные данные
Если желаемого распределения камней достичь нельзя, в первой строке вывести No solution. Иначе, в первой строке вывести одно целое число – минимальное количество ходов, за которое можно достичь желаемого распределения.