#include #include #include #include #include #include /*** * Exponencialni reseni */ using namespace std; vector< pair > villages; int main() { int N; scanf("%d", &N); int position; scanf("%d", &position); int hats = 0; for (int i = 0; i < N; ++i) { int index, order; scanf("%d%d", &index, &order); hats += order; villages.push_back(make_pair(index, order)); } sort(villages.begin(), villages.end()); vector > lefts; vector > rights; for (auto it = villages.begin(); it < villages.end(); ++it) { if (it->first > position) break; lefts.push_back(*it); } for (auto it = villages.end() - 1; it >= villages.begin(); --it) { if (it-> first <= position) break; rights.push_back(*it); } int best_energy = -1; int position_copy; int hats_copy; int energy; vector >* sorted_villages[] = {&lefts, &rights}; for (int i = 0; i < (1 << N); ++i) { int i_copy = i; position_copy = position; hats_copy = hats; energy = 0; unsigned long remainings[] = {lefts.size(), rights.size()}; for (int j = 0; j < N; ++j) { int dir = i_copy & 1; i_copy >>= 1; if (!remainings[dir]) goto end_of_outer_loop; pair* village = &sorted_villages[dir]->at(remainings[dir]-1); --remainings[dir]; energy += abs(village->first - position_copy) * hats_copy; hats_copy -= village->second; position_copy = village->first; } if (best_energy == -1 || energy < best_energy) { best_energy = energy; } end_of_outer_loop:; } printf("%d\n", best_energy); return 0; }