#include<bits/stdc++.h>
using namespace std;

class BridgeBuildingDiv2 {
public:
	int minDiameter(vector<int> a, vector<int> b, int k) {
		int nd = 0, sz = a.size() + 1;
		vector<vector<int> > dp(30, vector<int>(30, 1e9));
		for (int i = 0; i < a.size(); i++) {
			dp[nd][nd + 1] = dp[nd + 1][nd] = a[i];
			dp[nd][nd] = 0;
			dp[nd + 1][nd + 1] = 0;

			++nd;
		}

		++nd;
		for (int i = 0; i < b.size(); ++i) {
			dp[nd][nd + 1] = dp[nd + 1][nd] = b[i];
			dp[nd][nd] = 0;
			dp[nd + 1][nd + 1] = 0;
			++nd;
		}

		int ans = 1e9;
		for (int l = 0; l < (1 << sz); ++l) {
		if(__builtin_popcount(l)!=k)continue;
			for (int i = 0; i < sz; ++i)
				if (l & (1 << i))
					dp[i][i + sz] = dp[i + sz][i] = 0;
			for (int k = 0; k < sz * 2; ++k)
				for (int i = 0; i < sz * 2; ++i)
					for (int j = 0; j < sz * 2; ++j)
						dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			int tmp = 0;
			for (int i = 0; i < sz * 2; ++i)
				for (int j = 0; j < sz * 2; ++j)
					if (dp[i][j] < 1e9)
						tmp = max(tmp, dp[i][j]);
			ans = min(ans, tmp);
			for (int i = 0; i < sz; ++i)
				if (l & (1 << i))
					dp[i][i + sz] = dp[i + sz][i] = 1e9;
		}
		return ans;
	}
};