Electoral College Shenanigans

Given the division of Riddler Township into 10 unevenly populated shire, what is the lowest popular vote total that a winning candidate can achieve?
First, let's note that there are a total of $(3 + 4 + \dots + 12) = 75$ electors, so the winning candidate must amass at least $38$ electors.
If shire $k$ has population $P_k$, the lowest popular vote within shire $k$ for a winning candidate is achieved by receiving $\frac{P_k+1}{2}$ votes if shire $k$ is won and $0$ if shire $k$ is lost by that candidate.
Let $x_k \in \{0,1\}$ with $x_k=1$ denoting ``candidate wins shire $k$''. Then the minimal number of votes to achieve the outcome $x = (x_1, \dots, x_{10}) \in \{0,1\}^{10}$ is $$c(x) = \sum_{k=1}^{10} \frac{P_k+1}{2} x_k = \sum_{k=1}^{10} (5k+1) x_k.$$ Additionally, the formula for the number of electors achieved by the outcome $x$ is $E(x) = \sum_{k=1}^{10} (2+k) x_k.$
This electoral problem can be recast as the following knapsack problem:
$$\min \left\{ c(x) = \sum_{k=1}^{10} (5k+1) x_k : E(x) = \sum_{k=1}^{10} (2+k) x_k \geq 38, x \in \{0,1\}^{10} \right\}.$$ Solving this knapsack problem, we see that if a candidate wins $1-$, $2-$, $3-$, $4-$, $7-$, and $9-$shires with the minimal number of votes, then they would receive $38$ electors based on $136$ votes, or just $24.3\%$ of the popular vote.