秋招笔试-清理IDE（二）

// empty
#pragma once
#include "stdafx.h"
#include <limits.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <map>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include<set>
#include <vector>


/*
猿辅导第一题：
*/
#if 0

/*

2
12 A tidy tiger tied a tie tighter to tidy her tiny tail
1 a
16 A big black bug bit a big black bear made the big black bear bleed blood
2 b?? b???
*/

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void printMax(unordered_map<string, int>& umap) {
	vector<pair<string, int>> res(umap.begin(), umap.end());
	sort(res.begin(), res.end(), [](pair<string, int>& a, pair<string, int>& b) {return a.second > b.second; });
	cout << res[0].second << endl;
}

bool check(string& a, string& b) {
	if (a.size() != b.size())
		return false;

	int n = b.size();
	int i = 0, j = 0;
	while (i < n && j < n) {
		if (a[i] == b[j]) {
			++i;
			++j;
		}
		else {
			if (b[j] == '?') {
				++i;
				++j;
			}
			else {
				return false;
			}
		}
	}
	return true;
}

int main() {
	int m;
	cin >> m;

	for (int i = 0; i < m; i++) {
		vector<string> in;
		vector<string> stop_words;
		unordered_map<string, int> umap;
		int num1;
		cin >> num1;
		string str;
		for (int i = 0; i < num1; i++) {
			cin >> str;
			for (int i = 0; i < str.size(); i++) {
				if (str[i] >= 'a' && str[i] <= 'z') {
					str[i] = toupper(str[i]);
				}
			}

			in.push_back(str);
		}

		int num2;
		cin >> num2;
		string tar;
		for (int i = 0; i < num2; i++) {
			cin >> tar;
			for (int i = 0; i < str.size(); i++) {
				if (str[i] >= 'a' && str[i] <= 'z') {
					str[i] = toupper(str[i]);
				}
			}
			stop_words.push_back(tar);
		}

		for (int i = 0; i < in.size(); i++) {
			for (string& s : stop_words)
			{
				if (!check(in[i], s)) {
					umap[in[i]]++;
				}
			}
		}
		printMax(umap);
	}
}
#endif

#if 0

#include <string>
#include <iostream>

bool check(string& a, string& b) {
	if (a.size() != b.size())
		return false;
	int n = b.size();
	int i = 0, j = 0;
	while (i < n && j < n) {
		if (a[i] == b[j]) {
			++i;
			++j;
		}
		else {
			if (b[j] == '?') {
				++i;
				++j;
			}
			else {
				return false;
			}
		}
	}
	return true;
}

int main() {
	string a = "aaaabbs";
	string b = "aaa???s";
	if (check(a, b)) {
		cout << '-';
	}
	else {
		cout << '!';
	}
}

#endif // 1


#if 0
int fun1(int n) {
	vector<int> dp(n,0);
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i < n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n-1];
}

void fun2(vector<int>& arr) {
	
	int n = arr.size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n-1; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j+1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	cout << arr[n - 1] << " " << arr[n - 2] << " " << arr[n - 3] << " " << arr[n - 4] << endl;

}

//【1，4，，6，3，7，5，8，9】
// 1. 6.2 2， 6.7

float getDis(float num1,float num2) {
	float res = abs(num1 - num2);
	return res;
}

float findNum(vector<int>& vec,float num) {
	vector<float> temp;
	for (int val: vec) {
		float num_ = static_cast<float>(val);
		temp.push_back(num_);
	}
	float min = 420000000.0;
	for (int i = 0; i < temp.size(); i++) {
		if (min < getDis(temp[i], num))
			min = temp[i];
	}
	return min;
}

void temp() {
	float num = 6.2;
	vector<int> vec = { 1,4,6,3,7,5,8,9 };
	float min = 420000000;
	for (int i = 0; i < vec.size(); i++) {
		cout << "inter " << i << endl;
		float num1 = static_cast<float>(vec[i]);
		cout << "num:" << num1 << endl;
		float dis = getDis(num, 6.2);
		cout << "dis:" << dis << endl;
		if (dis < min)
		{
			min = vec[i];
		}
		cout << "min:" << min << endl;
	}
	cout << min << endl;
}

int main(){
	temp();
}

#endif

// 三个线程 顺序打印
#if 0

condition_variable cv;
mutex m;
int flag = 0;
int n = 10;

void printA() {
	unique_lock<mutex> loc(m);
	for (int i = 0; i < n; i++){
		cout << "A:" << i << endl;
	}
	flag = 1;
	loc.unlock();
	cv.notify_all();
	
}

void printB() {
	unique_lock<mutex> loc(m);
	while (flag != 1)
		cv.wait(loc);
	for (int i = 0; i < n; i++) {
		cout << "B:" << i << endl;
	}
	flag = 2;
	loc.unlock();
	cv.notify_all();
}

void printC() {
	unique_lock<mutex> loc(m);
	while (flag != 2)
		cv.wait(loc);
	for (int i = 0; i < n; i++) {
		cout << "C:" << i << endl;
	}
	loc.unlock();
	cv.notify_all();
}

int main()
{
	thread t1(printA);
	thread t2(printB);
	thread t3(printC);
	
	t1.detach();
	t2.detach();
	t3.detach();
	system("pause");
	return 0;
}

#endif // 1
 
// 三个线程 交替打印
#if 0

condition_variable cv;
mutex m;
int flag = 0;
int n = 10;

void printA() {
	
	for (int i = 0; i < n; i++) {
		unique_lock<mutex> loc(m);
		while (flag != 0) cv.wait(loc);
		cout << "A:" << i << endl;
		flag = 1;
		loc.unlock();
		cv.notify_all();
	}
}

void printB() {

	for (int i = 0; i < n; i++) {
		unique_lock<mutex> loc(m);
		while (flag != 1) cv.wait(loc);
		cout << "B:" << i << endl;
		flag = 2;
		loc.unlock();
		cv.notify_all();
	}
}

void printC() {

	for (int i = 0; i < n; i++) {
		unique_lock<mutex> loc(m);
		while (flag != 2) cv.wait(loc);
		cout << "C:" << i << endl;
		flag = 0;
		loc.unlock();
		cv.notify_all();
	}
}

int main()
{
	thread t1(printA);
	thread t2(printB);
	thread t3(printC);

	t1.detach();
	t2.detach();
	t3.detach();
	system("pause");
	return 0;
}

#endif // 1

// 生产者消费者模型
#if 0

#endif // 0

// 线程池的创建
#if 0



#endif // 0

//进制转换  将十进制转八，十六进制。
#if 0

void test1() {

	string s1;
	int a = 30;

	stringstream ss;
	ss << oct << a;        //10进制转成八进制读入流中，再以字符串输出
	ss >> s1;
	cout << s1 << endl;        //输出：36
	ss.clear();		//不清空可能会出错。


	ss << hex << a;		 //10进制转成十六进制读入流中，，再以字符串输出
	ss >> s1;
	cout << s1 << endl;        //输出：1e
}

int main() {

	test1();
}

#endif // 1


// 1. 归并排序
#if 0
/*
将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。
由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，
之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。

*/
void mergeSortCore(vector<int>& data, vector<int>& dataTemp, int low, int high) {

	if (low >= high) return;
	int len = high - low, mid = low + len / 2;
	int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;

	mergeSortCore(data, dataTemp, start1, end1);
	mergeSortCore(data, dataTemp, start2, end2);
	
	int index = low;

	while (start1 <= end1 && start2 <= end2) {
		dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];
	}

	while (start1 <= end1) {
		dataTemp[index++] = data[start1++];
	}


	while (start2 <= end2) {
		dataTemp[index++] = data[start2++];
	}

	for (index = low; index <= high; ++index) {
		data[index] = dataTemp[index];
	}
}


void mergeSort(vector<int>& data) {
	int len = data.size();
	vector<int> dataTemp(len, 0);
	mergeSortCore(data, dataTemp, 0, len - 1);
	for_each(data.begin(), data.end(), [](int& x) {cout << x << " "; });
}

int main() {
	vector<int> arr{10,15,1,5,1,5,2,44,1,5,41,5};
	mergeSort(arr);
	return 0;

}

#endif // 1

// 2. 快速排序
#if 0
/*
算法思想

1、选取第一个数为基准

2、将比基准小的数交换到前面，比基准大的数交换到后面

3、对左右区间重复第二步，直到各区间只有一个数

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，
所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，
让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
*/

void quickSort(vector<int>&numbers, int low, int high) {
	//  numbers = {10,8,4,6,9,10,123,6,2,14,3,8,5};
	if (low >= high) return;
	int first = low, last = high, key = numbers[low];

	while (first < last) {
		//从后往前找比他小的放前面,从前往后找比他大的放在后面，
		//以第一个数为基准，必须先从后往前走，再从前往后走

		while (first < last && numbers[last] >= key)
			last--;
		if (first < last) numbers[first++] = numbers[last];


		while (first < last && numbers[first] <= key)
			first++;
		if (first < last) numbers[last--] = numbers[first];

	}
	numbers[first] = key;

	quickSort(numbers, low, first - 1);
	quickSort(numbers, first + 1, high);
}

int main() {
	vector<int> numbers = { 10,8,4,6,9,10,123,6,2,14,3,8,5 };
	quickSort(numbers,0,numbers.size()-1);
	for_each(numbers.begin(), numbers.end(), [](int& num) {cout << num << " "; });

}

#endif // 1

// 3. 堆排序
#if 0

void heapify(vector<int>& nums, int n, int i)//对有一定顺序的堆，
											 //当前第i个结点取根左右的最大值（这个操作称heapfiy）
{
	int l = i * 2 + 1, r = i * 2 + 2;
	int max = i;
	if (l<n && nums[l]>nums[max])
		max = l;
	if (r<n && nums[r]>nums[max])
		max = r;
	if (max != i)
	{
		swap(nums[max], nums[i]);
		heapify(nums, n, max);
	}
}
void heapify_build(vector<int>& nums, int n)//建立大根堆，从树的倒数第二层第一个结点开始，
											//对每个结点进行heapify操作，然后向上走
{
	int temp = (n - 2) / 2;
	for (int i = temp; i >= 0; i--)
		heapify(nums, n, i);

	for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}

void heapify_sort(vector<int>& nums, int n)//建立大根堆之后，每次交换最后一个结点和根节点（最大值），
										   //对交换后的根节点继续进行heapify（此时堆的最后一位是最大值，因此不用管他，n变为n-1）
{
	heapify_build(nums, n);
	for (int i = 0; i < n; i++)
	{
		swap(nums.front(), nums[n - i - 1]);
		heapify(nums, n - i - 1, 0);
	}
}


int main() {
	vector<int> numbers = { 10,8,4,6,9,10,123,6,2,14,3,8,5 };
	heapify_sort(numbers,numbers.size());
	for (int i = 0; i < numbers.size(); i++)
	{
		cout << numbers[i] << " ";
	}

}


#endif // 0


// lambada 表达式测试
#if 0

int com = 10;

int main() {

	int num = 1;
	int val = 2;
	vector<int> res = {10,15,61,61,5,6,13,15,1};
	for_each(res.begin(), res.end(), [&](int& x) {cout << x + num << " "; });

}
#endif

#if 0

int com = 10;

int main() {

	int num = 1;
	int val = 2;
	vector<int> res = { 10,15,61,61,5,6,13,15,1 };
	sort(res.begin(), res.end(), [](int& a, int& b) {return a <= b; });
	for_each(res.begin(), res.end(), [&](int& x) {cout << x + num << " "; });

}
#endif



#if 0

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
using namespace std;



int main() {
	int n;
	cin >> n;
	vector<int> arr;

	int max = INT_MIN;
	int dis = INT_MAX;//最接近1
	int min_val;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		int dist = abs(num - 1);
		if (dist < dis) {
			dis = dist;
			min_val = num;
		}
		if (num > max) {
			max = num;
		}
		arr.push_back(num);
	}

	int res = 0;

	res = 7 - max;
	res += (abs(1 - min_val));

	int is_odd;

	int fisrt = 0;
	int second = 0;

	for (int i = 0; i < n; i++) {
		if (arr[i] == max && fisrt == 0) {
			fisrt = 1;
			continue;
		}
		if (arr[i] == min_val && second == 0) {
			second = 1;
			continue;
		}
		res += abs((arr[i] - 1));
	}
	cout << res;
}
#endif // 0

#if 0
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main() {
	string s;
	cin >> s;
	stack<char> st;
	int size = s.size();
	st.push(s[0]);
	for (int i = 1; i < size; i++) {
		char c = s[i];
		char top = st.top();
		if ((c == 's' && top == 'f') || (c == 'f' && top == 'w')) {
			st.pop();
		}
		else {
			st.push(c);
		}
	}
	int left = st.size();
	int res = size - left;
	cout << res;
}
#endif // 0


#if 0

#include<iostream>
#include<vector>
#include<string>

using namespace std;

void print(vector<vector<string>>& map, int n, int m) {
	for (int k = 0; k < n; k++) {
		for (int j = 0; j < m; j++) {
			cout << map[k][j] << " ";

		}
		cout << endl;
	}
}

int main() {
	int n, m, q;// 1 2 7
	cin >> n >> m >> q;
	string name;
	vector<vector<string>> map(n, vector<string>(m, "NULL"));//1 2 
	cout << q << endl;
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		int x, y;
		cin >> x >> y;
		if (t == 1) {//放置
			name.clear();
			cin >> name;
			if (x >= 0 && y >= 0 && x < n && y < m)// 1 2
			{
				if (map[x][y] == "NULL")
					map[x][y] = name;
			}
		}
		if (t == 2) {//移除
			if (x >= 0 && y >= 0 && x < n && y < m) {
				if (map[x][y] != "NULL") {
					map[x][y] = "NULL";
				}
			}
		}
		cout << "第" << i + 1 << "次：" << x << "," << y << " " << name << " " << map[0][1] << " " << map[0][2];
	}

	for (int k = 0; k < n; k++) {
		for (int j = 0; j < m; j++) {
			cout << map[k][j] << " ";
		}
		cout << endl;
	}
	//for (int k = 0; k < n; k++) {
	//	for (int j = 0; j < m; j++) {
	//		cout << map[k][j] << " ";
	//	}
	//	cout << endl;
	//}

}
#endif

#if 0

#include "stdafx.h"
#include <limits.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <map>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include<set>

using namespace std;
set<string> res;

bool check(string& s, int tar) {
	int count = 0;
	for (char c : s) {
		int val = (c - '0');
		if (val == 1)
			count++;
	}
	if (count == tar)return true;
	else return false;

}

void backtrack(string& s,int num,int startIndex) {
	if (check(s, num)) {
		res.insert(s);
		return;
	}
	for (int i = 0; i < s.size(); i++) {
		s[i] = 1;
		backtrack(s, num, startIndex);
		s[i] = 0;
	}
}

string b2s(string& s) {
	string hours = s.substr(0,4); 
	string minutes = s.substr(4,6);
	cout << "h:" << hours;
	cout << "s:" << minutes;
	return "";
}

int main() {

	string s = "0000000000";
	set<string> res;
	res.insert(string("asd"));
	res.insert("asdds");
	res.insert("ffgasdfa");
	res.insert("asdfasd");
	for (string s : res)cout << s <<" ";
	cout << res.size()<<endl;
	return 0;
}
#endif // 1



#if 0
#include<iostream>
#include<string>

using namespace std;

int main() {
	string s;
	cin >> s;
	int res = 0;
	for (int i = 1; i <= s.size()-2; i++) {
		if (s[i] != s[i - 1] && s[i] != s[i + 1]) {
			continue;
		}
		else {
			if (s[i] == s[i - 1]) {
				s[i] = s[i + 1];
				s.erase(s[i-1]);
				res++;
				continue;
			}else if(s[i] == s[i + 1]) {
				s[i] = s[i - 1];
				s.erase(s[i + 1]);
				res++;
			}
		}
	}

	cout << res;
}

#endif

#if 0

/*
5
1 2 5 2 8
*/

#include<iostream>
#include<vector>

using namespace std;

long long res = 0;
long long color_nums = 0;


bool check(const vector<int>& vec, const vector<int>& color) {
	vector<int> res;
	for (int i = 0; i < color.size(); i++) {
		if (color[i] == 1) {
			res.push_back(vec[i]);
		}
	}

	for (int i = 0; i < res.size(); i++) {
		for (int j = i + 1; j < res.size(); j++) {
			if ((res[i] + res[j]) % 2 == 0)
				continue;
			else
				return false;
		}
	}
	return true;

}

void tranverse(vector<int>& arr, vector<int>& color, int start) {
	if (color_nums >= 2) {
		if (check(arr, color)) {
			res++;
		}
		else {
			return;
		}
		if (color_nums = color.size()) {
			return;
		}
	}
	for (int i = start; i < color.size(); i++) {
		color[i] = 1;
		tranverse(arr, color, start + 1);
		color[i] = 0;
	}
}
int main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	vector<int> color(n, 0);

	for (int i = 0; i < n; i++) {
		int val;
		cin >> val;
		arr[i] = val;
	}

	tranverse(arr, color, 0);

	res = res % (1000000000 + 7);
	cout << res;
}
#endif // 0


#if 0
#include<iostream>
#include<vector>
#include<map>
#include<string>

using namespace std;

string path = "";
string res;
void dfs(string& s, int k, int tar, int start) {
	if (k == tar) {
		res = path;
		return;
	}
	for (int i = start; i < 26; i++) {
		char c = 'a' + i;
		path.push_back(c);
		dfs(s, k++, tar, start++);
		path.pop_back();
	}
}

int main() {
	int k;
	cin >> k;
	vector<int> mp;
	for (int i = 0; i < 26; i++) {
		mp.push_back(i + 1);
	}
	string ret;
	for (char c : res) {
		int index = c - 'a';
		int val = mp[index];
		string val_ = to_string(val);
		ret += val_;
	}


	cout << -1;
}
#endif // 1

#if 0
/*
第一行一个正整数n，表示宝藏数量。

第二行为n个正整数p1, p2,...... pn，其中pi表示第 i 个宝藏在序号为pi的房间。

第三行为n个正整数w1, w2,...... wn，其中wi表示第i个宝藏的价值为wi。

数字间两两有空格隔开

1 ≤ n ≤ 40000, 1 ≤ pi ＜230, 1 ≤ wi ≤ 106。

输出一个正整数表示能获得的宝藏价值之和的最大值。

4
2 3 4 5
2 5 2 4

6

*/

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;


int gcd(int m, int n) {
	while (m != n)
	{
		if (m<n)
			n = n - m;
		else
			m = m - n;
	}
	return m;
}

int sum(vector<vector<int>>& matrix,int row,int col,int k) {
	int res = 0;
	for (int i = row; i < row + k; i++) {
		for (int j = col; j < col + k; j++) {
			res += matrix[i][j];
		}
	}
	cout <<"res"<< res<<endl;
	return res;
}

int main() {

	int n, m, k;
	cin >> n >> m >> k;
	
	vector<vector<int>> matrix(n+1, vector<int>(n+1, 0));

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++) {
			matrix[i][j] = gcd(i,j);
			cout << matrix[i][j] << " ";
		}
		cout << endl;
	}
	int ret = 0;

	for (int i = 1; i <= n && (i + k - 1 <= n); i++) {
		for (int j = 1; j <= m && (j + k - 1 <= m); j++) {
			ret += sum(matrix, i, j, k);
		}
	}

	cout << ret << endl;
	return 0;

}

#endif

#if 0


#include<iostream>
#include<vector>
using namespace std;

int main() {
	using ll = long long;
	ll a, b, c;
	cin >> a >> b >> c;
	ll size_a = a%c;
	ll size_b = c%c;
	ll result;
 
	result = min(size_a,size_b);
	result = min(result, c - size_a);
	result = min(result, c - size_b);
	cout << 2 * result;
	return 0;
}

#endif

#if 0
#include <limits.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <map>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include<set>

using namespace std;

int main() {

	return 0;
}

#endif

#if 0
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a;
	vector<int> b;
	for (int i = 0; i < n; i++) {
		int val;
		cin >> val;
		a.push_back(val);
	}
	for (int i = 0; i < n; i++) {
		int valb;
		cin >> valb;
		b.push_back(valb);
	}
	vector<vector<int>> dp(n, vector<int>(3, 0));
	dp[0][0] = 0;
	dp[0][1] = a[0];
	dp[0][2] = b[0];
	int res = 0;
	for (int i = 1; i < n; i++) {
		dp[i][0] = max(max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][0]);
		dp[i][1] = max(dp[i - 1][0] + a[i], dp[i - 1][2] + a[i]);
		dp[i][2] = max(dp[i - 1][0] + b[i], dp[i - 1][1] + b[i]);
	}
	res = max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
	cout << res;
}
#endif

#if 0

int main() {
	int n;
	cin >> n;
	
}

#endif

#if 0
#pragma once
#include "stdafx.h"
#include <limits.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <map>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <set>


using namespace std;

int main() {
	int m, n, k;

	string str1;
	istringstream ss(str1);
	getline(cin, str1);
	string temp1;
	vector<int> ins;
	while (getline(ss, temp1, ' ')) {
		ins.push_back(stoi(temp1));
	}
	m = ins[0];
	n = ins[1];
	k = ins[2];

	vector<int> indexes;
	string str;
	getline(cin, str);
	istringstream sin(str);
	string temp;
	while (getline(sin,temp,' ')){
		indexes.push_back(stoi(temp));
	}
	cout << m << n << k;
	cout << endl;
	cout << str;
	system("pause");
	return 0;
}

#endif

#if 0

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int m, n;
	cin >> m >> n;
	vector<int> p(n, 0);
	vector<int> q(m, 0);
	vector<int> s(m, 0);

	map<int, int> umapq;

	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> q[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> s[i];
	}

	for (int i = 0; i < q.size(); i++) {
		umapq[q[i]] = i;
	}
	unordered_map<int, int> res;
	sort(p.begin(), p.end(), [](int a, int b) {return a > b; });

	map<int, int>::reverse_iterator it;
	for (it = umapq.rbegin(); it != umapq.rend(); it++) {
		for (int i = 0; i < p.size(); i++) {
			if (it->first < p[i]) {
				res[i] += s[it->second];
				break;
			}
		}
	}
	
	int time = 0;
	int max_val = INT_MIN;
	for (pair<const int, int>& item : res) {
		if (item.second > max_val)
			max_val = item.second;
		cout << "res:" << item.second << endl;
	}
	time = max_val;
	cout << time;
	return 0;
}

#endif

#if 0
#include<iostream>
#include<vector>
using namespace std;

int time = INT_MAX;
unordered_map<int, int> res;

int fail = 0;

/*
5 2
5 3
1 4 5 2 3
1 6 10 3 4

16
*/


void tranverse(vector<int>& p,vector<int>& q,vector<int>& s,int index,int n,int m) {
	if (index >= m) {
		int max_val = INT_MIN;
		for (int i = 0; i < n; i++) {
			if (res[i] > max_val)
				max_val = res[i];
		}
		if (max_val < time) {
			time = max_val;
		}
		return;
	}
	for (int i = 0; i < n; i++) {
		if (p[i] > q[index]) {
			res[i] += s[index];
			tranverse(p, q, s, index + 1, n, m);
			res[i] -= s[index];
		}
	}
}

int main()
{
	int m, n;
	cin >> m >> n;
	vector<int> p(n, 0);
	vector<int> q(m, 0);
	vector<int> s(m, 0);

	map<int, int> umapq;

	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> q[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> s[i];
	}
	tranverse(p, q, s, 0,n, m);
	cout << time;
}



#endif

#if 0
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main() {
	int t;
	cin >> t;
	vector<string> vec;
	for (int i = 0; i < t; i++) {
		string str;
		cin >> str;
		vec.push_back(str);
	}

	for (string& str : vec) {
		int flag = 1;
		int counts = 0;
		while (flag) {
			int stop = 0;
			for (int i = 1; i < str.size(); i++) {
				if (str[i] == str[i - 1]) {
					char a = str[i];
					char b = str[i - 1];
					str.erase(a);
					str.erase(b);
					counts++;
					stop++;
				}
			}
			if (stop == 0) {
				flag = 0;
			}
		}
		if (counts % 2 == 1)cout << "Yes";
		else cout << "No";
	}
}
#endif

# if 0
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
	int getZeroNum(int val) {
		string s = to_string(val);
		cout << s << endl;
		int n = s.size() - 1;
		int res = 0;
		while (s[n]=='0') {
			res++;
			n--;
		}
		return res;
	}
	int ret = 0;
	int getSubarrayNum(vector<int>& a, int x) {
		// write code here
		int prod = 1;
		for (int i = 0; i < a.size(); i++) {
			for (int j = i; j < a.size(); j++) {
				prod = prod*a[j] % (1000000007);
				if (getZeroNum(prod) >= x) {
					cout << ":" << prod;
					ret = (ret + 1) % 1000000007;
				}
			}
			prod = 1;
		}
		return ret;
	}
};

struct A {
	void f(int i) {
		cout << "A" << endl;
	}
};

struct B : public A {
	void f(int i, int j) {
		cout << "B" << endl;
	}
};

int main() {
	B b;
	b.A::f(1);
	b.f(1, 1);
	b.A::f(1);

	int a[] = { 1,2,3 };
	int *p = a;
	//*++p += *(p++) * 2;
	//a[1] = (a[1]++) * 2;
	a[1] = a[2] * 2;
	// 1 6 3
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
	return 0;

}

#endif

#if 0

#include<iostream>
#include<vector>
#include<utility>
#include<unordered_map>
#include<stack>
#include<algorithm>

using namespace std;

void isPerfect(vector<int>& orders, vector<int>& scores, int m, int j, int k) {
	unordered_map<int, int> umap; // index - score
	for (int i = 0; i < m; i++) {
		umap[orders[i]] = scores[i];
	}
	vector<int> vec1 = orders;
	vector<int> vec2;
	bool res = false;
	while (vec1.size() != 1) {
		if (res) {
			break;
		}
		for (int i = 1; i < m; i += 2) {
			if (orders[i] == j && orders[i - 1] == k) {
				res = true;
				break;;
			}
			if (orders[i] == k && orders[i - 1] == j) {
				res = true;
				break;;
			}
			if (umap[orders[i]] > umap[orders[i - 1]]) {
				vec2.push_back(orders[i]);
			}
			else {
				vec2.push_back(orders[i - 1]);
			}
		}
		vec1 = vec2;
		vec1.clear();
		vec1.assign(vec2.begin(), vec2.end());
		for_each(vec1.begin(), vec1.end(), [](int x) {cout << x << " "; });
		cout << vec1.size();
		break;
		cout << endl;
		vec2.clear();
	}
	if (res == true)
		cout << "YQST" << endl;
	else
		cout << "..." << endl;
}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int m, j, k; // 一共m个车， 受关注的两辆车 j  k  
		cin >> m >> j >> k;
		vector<int> orders(m, 0);
		vector<int> scores(m, 0);

		for (int i = 0; i < m; i++) {
			cin >> orders[i];
		}
		for (int i = 0; i < m; i++) {
			cin >> scores[i];
		}
		isPerfect(orders, scores, m, j, k);
	}
	return 0;
}

#endif

#if 0
#include<iostream>
#include<vector>
#include<utility>
#include<unordered_map>
#include<stack>
#include<algorithm>

using namespace std;

void getmemory(char *p) {
	p = (char *)malloc(100);

}

void test() {
	char *str = NULL;
	getmemory(str);
	cout << sizeof(str) << endl;
	strcpy(str,"hello world");
	printf("%s\n",str);
}

int main() {
	test();
	return 0;
}

#endif

#if 0
#include<iostream>
#include<vector>
#include<utility>
#include<unordered_map>
#include<stack>
#include<algorithm>
#include<sstream>
using namespace std;



void getUrlQueryByKey(string url) {
	// write code here
	int i = 0;
	while (url[i] != '?') {
		i++;
	}
	string str(url.begin() + i, url.end());
	cout << url;
}

int main() {
	string s;
	cin >> s;
	getUrlQueryByKey(s);
	return 0;
}
#endif


// tecent no.1  90% 
#if 0
/**
* struct ListNode {
*	int val;
*	struct ListNode *next;
*	ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
	ListNode* xorList(ListNode* a, ListNode* b) {
		// write code here
		int len_a = 0;
		int len_b = 0;
		ListNode* heada = a;
		ListNode* headb = b;
		string sa = "";
		string sb = "";
		while (heada) {
			if (heada) {
				sa += to_string(heada->val);
			}
			heada = heada->next;
			len_a++;

		}
		//         cout<<len_a<<endl;
		//         cout<<sa<<endl;
		while (headb) {
			if (headb) {
				sb += to_string(headb->val);
			}
			headb = headb->next;
			len_b++;

		}
		//         cout<<len_b<<endl;
		//         cout<<sb<<endl;
		reverse(sb.begin(), sb.end());
		int diff;
		if (len_a >= len_b) {
			diff = len_a - len_b;
			for (int i = 0; i < diff; i++) {
				sb.insert(sb.begin(), '0');
			}
		}
		else {
			diff = len_b - len_a;
			for (int i = 0; i < diff; i++) {
				sa.insert(sa.begin(), '0');
			}
		}
		string res = "";
		for (int i = 0; i < max(len_a, len_b); i++) {
			if (sa[i] == sb[i]) {
				res += '0';
			}
			else {
				res += '1';
			}
		}
		int index = 0;
		while (res[index] == '0') {
			index++;
		}
		string ret(res.begin() + index, res.end());
		cout << ret << endl;
		ListNode* head_ret = new ListNode(-1);
		ListNode* dummy = head_ret;
		for (int i = 0; i < ret.size(); i++) {
			int val = ret[i] - '0';
			ListNode* node = new ListNode(val);
			dummy->next = node;
			dummy = dummy->next;
		}

		return head_ret->next;
	}

};

#endif


// tecent no.2  回溯暴力 33.33%
#if 0
#include<iostream>
#include<vector>
#include<bitset>
#include<limits.h>

using namespace std;

int res = INT_MAX;

int qiuhe(vector<int>& nums) {
	int res = 0;
	for (int val : nums)
		res += val;
	return res;
}

void tranverse(vector<int>& nums, int index, int k) {
	if (index == k) {
		int he = qiuhe(nums);
		res = min(res, he);
		return;
	}
	for (int i = 0; i < nums.size(); i++) {
		bitset<32> val(nums[i]);
		int ori = nums[i];
		int cnt = val.count();
		nums[i] = cnt;
		tranverse(nums, index + 1, k);
		nums[i] = ori;
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> nums(n, 0);
	for (int i = 0; i < n; i++) {
		int val;
		cin >> val;
		nums[i] = val;
	}
	tranverse(nums, 0, k);
	cout << res;
}
#endif

// tecent no.3  输出-1 16.67%
#if 0

#include<iostream>
#include<vector>
#include<bitset>
#include<limits.h>

using namespace std;

int main() {
	int n, x;
	cin >> n >> x;
	vector<int> x1(n, 0);
	vector<int> w1(n, 0);
	vector<int> x2(n, 0);
	vector<int> w2(n, 0);
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		x1[i] = a;
		w1[i] = b;
		x2[i] = c;
		w2[i] = d;
	}


	cout << -1;
}

#endif

// tecent no. 4   deque模拟 100%
#if 0
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;

int main() {
	int n;
	cin >> n;
	deque<int> arr(n, 0);
	for (int i = 0; i < n; i++) {
		int val;
		cin >> val;
		arr[i] = val;
	}
	vector<int> shunxu;
	int front;
	int back;
	for (int i = 0; i < n; i++) {
		front = arr.front();
		back = arr.back();
		if ((i + 1) % 2 == 1) {
			if (front > back) {
				shunxu.push_back(front);
				arr.pop_front();
			}
			else {
				shunxu.push_back(back);
				arr.pop_back();
			}
		}
		else {
			if (front < back) {
				shunxu.push_back(front);
				arr.pop_front();
			}
			else {
				shunxu.push_back(back);
				arr.pop_back();
			}
		}
	}
	int len = shunxu.size() - 1;
	for (int i = 0; i < len; i++) {
		cout << shunxu[i] << " ";
	}
	cout << shunxu[len];
	return 0;
}
#endif

// tecent no.5   随便输出n, 18.18%
#if 0
#include<iostream>

using namespace std;

int main() {



	int n;
	cin >> n;
	cout << n;
}
#endif


#if 0
#include<vector>
#include<iostream>
using namespace std;

bool isSelf(vector<vector<int>>& matrix,int x1,int y1,int x2,int y2) {
	int i = x1, j = y1;
	bool res = true;
	for (; i < x2; i++) {
		if (matrix[i][i] != 1) {
			res = false;
		}
	}
	return res;
}

bool isSym(vector<vector<int>> matrix,int x1,int y1,int x2,int y2) {
	bool res = true;
	for (int i = x1; i < x2; i++) {
		for (int j = y1; j < y2; j++) {
			if (matrix[i][j] != matrix[j][i]) {
				res = false;
				break;
			}
		}
	}
	return res;
}

int findAllArray(vector<vector<int>>& arr) {
	int rows = (int)arr.size();
	int cols = (int)arr[0].size();
	int res = 0;

	int n = rows;
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			for (int w = 0; w < n; w++) {
				if (i+w<n && j+w <n) {
					if(isSelf(arr, i, j, i + w, j + w) && isSym(arr, i, j, i + w, j + w))
						res++;
				}
			}
		}
	}
	return res;
}

int main(){
	vector<vector<int>> arr = { {1,1,1},{1,1,1},{0,1,1} };
	int ret = 0;
	ret = findAllArray(arr);
	cout << ret << endl;
}
#endif


#if 0

#include<vector>
#include<iostream>
using namespace std;

bool isSelf(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2) {
	int i = x1, j = y1;
	bool res = true;
	for (; i < x2; i++) {
		if (matrix[i][i] != 1) {
			res = false;
		}
	}
	return res;
}

bool isSym(vector<vector<int>> matrix, int x1, int y1, int x2, int y2) {
	bool res = true;
	for (int i = x1; i < x2; i++) {
		for (int j = y1; j < y2; j++) {
			if (matrix[i][j] != matrix[j][i]) {
				res = false;
				break;
			}
		}
	}
	return res;
}

int findAllArray(vector<vector<int>>& arr) {
	int rows = (int)arr.size();
	int cols = (int)arr[0].size();
	int res = 0;

	int n = rows;
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			for (int w = 0; w < n; w++) {
				if (i + w<n && j + w <n) {
					if (isSelf(arr, i, j, i + w, j + w) && isSym(arr, i, j, i + w, j + w))
						res++;
				}
			}
		}
	}
	return res;
}

int main() {
	vector<vector<int>> arr = { { 1,1,1 },{ 1,1,1 },{ 0,1,1 } };
	int ret = 0;
	ret = findAllArray(arr);
	cout << ret << endl;
}
#endif


#if 1
#include<vector>
#include<iostream>
using namespace std;

int findAllArray(int n) {
	int total = n*n;
	int left = (total - n)/2;
	int res = 1;
	for (int i = 0; i < left; i++) {
		res = res * 2;
	}
	return res;
}

int main() {
	int ret = 0;

	cout << ret << endl;
}
#endif