Commander's Dilemma

Problem Statement

Commander's Dilemma Problem Description The nation of Eryndor is at war. Its territory consists of N cities connected by M bidirectional roads. The cities are numbered from 1 to N, and each city has a strategic value. Once a city is defended, every city directly connected to it by a single road is automatically considered secured, and the enemy avoids secured cities. Because a secured city is already protected, the generals never place a garrison in a city adjacent to one they have already chosen. The generals must choose a set of cities to defend so that no two chosen cities are joined by a road . Their score is the total strategic value of the cities they chose — cities that merely become secured as a side effect contribute nothing. Determine the maximum score the generals can achieve. Input Format The first line contains two space-separated integers N and M — the number of cities and the number of roads. The second line contains N space-separated integers V 1 , V 2 , ...