You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

注意：本题调度次数可不只为1次。

阿强获得了到中国铁路总公司济南铁路局第一三一铁路线（青岛北铁

路枢纽）调度处参观学习的机会。今天他将学习的是动车组机动车头的区

段整编。

第一三一铁路线在青岛北铁路枢纽有 n 个路段，每个路段停放了半组

动车组列车，这些列车的车头朝东或西停靠。两个朝向不同的车头可以通

过连接若干节车厢整编成一列动车。为了方便调度，“0”表示朝西的车

头，用“1”表示朝东的车头。车辆整编被描述为以下过程：选择一对列车

头，将他们的位置更换，代价是两个车头附带车厢的数量𝑎𝑖+𝑏𝑖。

现在处长要求阿强破解调度系统的最优解功能。调度的最优解被定义

为完成调度后，所有可以整编成一列动车的车头对数（即逆序对数）减去

总调度代价。

【输入格式】

第一行一个正整数𝑛。

第二行为一个长度为𝑛的 01 串，表示车头朝向。

第三行为𝑛个整数𝑐𝑖，表示这个车头附带的车厢数量。

【输出格式】

一行一个整数，表示调度最优解。

【样例输入】

6
101010
1 1 1 1 1 1

【样例输出】

7

【数据范围】

对于 30%的数据，1≤ 𝑛 ≤8;

对于 50%的数据，1≤ 𝑛 ≤20；

对于 70%的数据，1≤ 𝑛 ≤550；

另有 20%数据，𝑐𝑖= 1或𝑐𝑖= 0；

对于 100%的数据1≤ 𝑛 ≤2512，0≤ 𝑐𝑖≤100；