/*
TASK: A Plus B_Dijkstra
LANG: CPP
AUTHOR: PeaTT~
*/
#include "aplusb.h"
#include <bits/stdc++.h>
#define tiii tuple<int,int,int>
#define pii pair<int,int>
using namespace std;
vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
vector<int> ans;
priority_queue<tiii,vector<tiii>,greater<tiii>> pq;
set<pii> mark;
pq.push({A[0]+B[0],0,0});
mark.insert({0,0});
while (ans.size() < N) {
auto [w,i,j] = pq.top();
pq.pop();
ans.push_back(w);
if(i+1 < N && !mark.count({i+1,j})) {
pq.push({A[i+1]+B[j],i+1,j});
mark.insert({i+1,j});
}
if (j+1 < N && !mark.count({i,j+1})) {
pq.push({A[i]+B[j+1],i,j+1});
mark.insert({i,j+1});
}
}
return ans;
}
