#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
constexpr double inf = 1e18;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<double>> dp(n, vector<double>(k + 1, inf));
dp[0][0] = 0;
for (int i = 0; i < h; i++) {
assert(x[i] == i);
assert(y[i] == i + 1);
// i, i + 1, c[i]
for (int j = 0; j <= k; j++) {
dp[i + 1][j] = dp[i][j] + c[i];
}
if (arr[i + 1] == 0) {
for (int j = 0; j <= k; j++) {
if (dp[i][j] != inf) {
dp[i + 1][j] = 0;
}
}
continue;
}
if (arr[i + 1] == 2) {
for (int j = 0; j < k; j++) {
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], (dp[i][j] + c[i]) / 2);
}
}
if (arr[i + 1] == 2 && arr[i] == 2) {
for (int j = 0; j < k; j++) {
for (int s = 2; j + s <= k; s += 2) {
double x = dp[i][j];
for (int _ = 0; _ < s; _++) {
x += c[i];
x /= 2;
}
dp[i + 1][j + s] = min(dp[i + 1][j + s], x);
}
}
}
}
return ranges::min(dp[h]);
}
