#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



/* Global output controls */

#define OC1 0
#define OC2 0



/* Store all the things */

#define MAX_THINGS 4096
static char store[MAX_THINGS];

/* A punned type for row,column coordinate pairs, allowing them to
 * be used either separately as individual coordinates or together
 * as reading-order sort keys */

union location {
	struct {
	#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
		uint8_t col;
		uint8_t row;
	#else
		uint8_t row;
		uint8_t col;
	#endif
	};
	uint16_t all;
};

/* Some of the things are things that do things */

#define MAX_ACTORS 256
static struct actor {
	union location loc;
	char dead;
	char team;
	int16_t hit_points;
	char attack_power;
	char padding;
} actors[MAX_ACTORS], *new_actor = actors;

/* In teams */

#define ELF 'E'
#define GOBLIN 'G'
#define INITIAL_HP 200
#define INITIAL_AP 3

/* Actors play on a notionally rectangular stage */

#define SINTX_MAX(type) ((((type) 1 << (sizeof (type) * CHAR_BIT - 2)) - 1) * 2 + 1)
#define UINTX_MAX(type) ((type) ~ (type) 0)
#define INTX_MAX(type) ((type) -1 < 0? SINTX_MAX(type): UINTX_MAX(type))
#define VAL_MAX(int_expr) INTX_MAX(typeof (int_expr))

#define MAX_ROWS VAL_MAX(((union location *)0)->row) + 1
#define MAX_COLS VAL_MAX(((union location *)0)->col) + 1

static char *stage[MAX_ROWS], **last_row;



/* Get character from stage at location */

static char inline char_at(union location loc) {
	return stage[loc.row][loc.col];
}

/* Put character on stage at location */

static void inline show_at(union location loc, char c) {
	stage[loc.row][loc.col] = c;
}

/* Put character on stage at location of actor */

static void inline show_for(struct actor *a, char c) {
	show_at(a->loc, c);
}

/* Location movements */

static inline union location go_up(union location l) {
	l.row -= 1; return l;
}

static inline union location go_left(union location l) {
	l.col -= 1; return l;
}

static inline union location go_right(union location l) {
	l.col += 1; return l;
}

static inline union location go_down(union location l) {
	l.row += 1; return l;
}

/* Location bounds checks */

static inline int can_go_up(union location l) {
	return l.row > 0 && l.col < stage[l.row] - stage[l.row - 1];
}

static inline int can_go_left(union location l) {
	return l.col > 0;
}

static inline int can_go_right(union location l) {
	return char_at(go_right(l)) >= ' '; /* null or newline marks end of row */
}

static inline int can_go_down(union location l) {
	return l.row < last_row - stage;
}

/* Look at all the things */

void see_stage() {
	printf("---\n%s", store);
}

/* and their innards */

void see_actors() {
	puts("");
	for (int row = 0; row <= last_row - stage; row++) {
		char *separator = "";
		for (struct actor *a = actors; a < new_actor; a++) {
			if (a->loc.row == row) {
				printf("%s%2d %2d %s%c(%3d)",
					separator,
					a - actors,
					a->loc.col,
					"~"+!a->dead,
					a->team,
					a->hit_points
				);
				separator = ";  ";
			}
		}
		putchar('\n');
	}
}

/* A sort comparator for actors */

static int actor_cmp(const void *a, const void *b) {
	const struct actor *a_ = a, *b_ = b;
	int result = a_->dead - b_->dead;
	if (!result) result = a_->loc.all - b_->loc.all;
	return result;
}

/* Sort actors */

static void sort_actors() {
	qsort(actors, new_actor - actors, sizeof (struct actor), actor_cmp);
}

/* Look up an actor by location. Can't rely on actors being sorted
 * every time this will be needed, so it has to be a linear search.
 * Should boil down to a SCASW instruction on x86 with any luck. */

static inline struct actor *actor_at(union location loc) {
	for (struct actor *a = actors; a < new_actor; a++) {
		if (a->loc.all == loc.all && !a->dead) return a;
	}
	return 0;
}



/* Get all the things */

#define ELF_KILLED 6
#define IO_ERROR 5
#define MAP_TOO_BIG 4
#define TOO_MANY_ROWS 3
#define ROW_TOO_WIDE 2
#define TOO_MANY_ACTORS 1
static int build_world(char pathname[], int elf_power) {
	if (0) printf ("%d\n%d\n", MAX_ROWS, MAX_COLS);
	int error = IO_ERROR;
	FILE *input = fopen(pathname, "r");
	if (input) {
		error = MAP_TOO_BIG;
		store[fread(store, 1, sizeof store - 1, input)] = '\0';
		if (feof(input)) {
			int need_another_row = 0;
			last_row = stage;
			new_actor = actors;
			error = 0;
			for (char *p = *last_row = store; *p; p++) {
				if (need_another_row) {
					if (last_row - stage >= MAX_ROWS - 1) {
						error = TOO_MANY_ROWS;
						break;
					}
					else {
						*++last_row = p;
						need_another_row = 0;
					}
				}
				if (0) printf("---\n[%d][%d]:'%c'\n", last_row - stage, p - *last_row, *p);
				if (*p == '\n') {
					need_another_row = 1;
				}
				else if (p - *last_row >= MAX_COLS) {
					error = ROW_TOO_WIDE;
					break;
				}
				else if (*p == ELF || *p == GOBLIN) {
					if (new_actor - actors >= MAX_ACTORS) {
						error = TOO_MANY_ACTORS;
						break;
					}
					else {
						struct actor *a = new_actor++;
						a->loc.col = p - *last_row;
						a->loc.row = last_row - stage;
						a->team = *p;
						a->dead = 0;
						a->hit_points = INITIAL_HP;
						a->attack_power = INITIAL_AP;
						if (*p == ELF) a->attack_power = elf_power;
						a->padding = 0;
					}
				}
				if (0) see_stage(), see_actors();
			}
		}
		fclose(input);
	}
	if (OC1) see_stage(), see_actors();
}



/* Find an enemy within range */

static struct actor *enemy_in_range(struct actor *a) {
	int weakest = INT_MAX;
	struct actor *enemy = 0;
	#define check(way)						\
	if (can_go_##way(a->loc)) {					\
		union location loc = go_##way(a->loc);			\
		char c = char_at(loc);					\
		if ((c == ELF || c == GOBLIN) && c != a->team) {	\
			struct actor *e = actor_at(loc);		\
			if (e->hit_points < weakest) {			\
				weakest = e->hit_points;		\
				enemy = e;				\
			}						\
		}							\
	}
	check(up)
	check(left)
	check(right)
	check(down)
	#undef check
	return enemy;
}



/* Actor fight enemy */

static int attack(struct actor *boxer, struct actor *raptor) {
	int result = 0;
	show_for(boxer, '@');
	show_for(raptor, '!');
	if (OC1) see_stage(), see_actors();
	if ((raptor->hit_points -= boxer->attack_power) <= 0) {
		raptor->dead = 1;
		show_for(raptor, '~');
		if (raptor->team == ELF) result = ELF_KILLED;
	}
	if (OC1) see_stage(), see_actors();
	show_for(boxer, boxer->team);
	if (raptor->dead) show_for(raptor, '.');
	else show_for(raptor, raptor->team);
	if (OC1) see_stage(), see_actors();
	return result;
}



/* Now for the algorithm that this entire scenario was an excuse for */

#define NO_ENEMIES 2
#define NO_ENEMY 1
int approach_enemy(struct actor *a) {
	static union location queue[MAX_THINGS];
	union location *head = queue, *tail = queue;
	union location *in_range_list;
	union location adj, target;
	int searching = NO_ENEMY;

	/* Add all enemy locations to the queue */

	for (struct actor *e = actors; e < new_actor; e++) {
		if (e->team != a->team && !e->dead) {
			*tail++ = e->loc;
		}
	}

	/* If there were no enemies there is no more to do */

	if (tail == queue) return NO_ENEMIES;

	/* Mark and queue all possible in-range locations */

	for (in_range_list = tail; head < in_range_list; head++) {
		#define check(way)				\
		if (						\
			can_go_##way(*head) &&			\
			char_at(adj = go_##way(*head)) == '.'	\
		) {						\
			show_at(adj, '?');			\
			*tail++ = adj;				\
		}
		check(up)
		check(left)
		check(right)
		check(down)
		#undef check
	}
	if (OC1) see_stage(), see_actors();

	/* Flood-fill the stage starting from own location until
	 * the edge of the flood touches an in-range location.
	 * Do the flood in waves where all the locations added
	 * during any given wave are equally distant from the
	 * actor, and stop adding new waves once an in-range
	 * location has been encountered. During the last wave,
	 * remember the in-range location that's first in
	 * reading order. */

	head = tail;
	*tail++ = a->loc;
	target.row = MAX_ROWS - 1;
	target.col = MAX_COLS - 1;
	while (searching && head < tail) {
		union location *wave_tail = tail;
		while (head < wave_tail) {
			union location loc = *head++;
			#define check(way, marker)				\
			if (can_go_##way(loc)) {				\
				switch (char_at(adj = go_##way(loc))) {		\
				case '?':					\
					searching = 0;				\
					if (adj.all < target.all) target = adj;	\
					show_at(adj, marker);			\
					break;					\
				case '.':					\
					show_at(adj, marker);			\
					*tail++ = adj;				\
				}						\
			}
			check(up, 'v')
			check(left, '>')
			check(right, '<')
			check(down, '^')
			#undef check
			if (0) see_stage(), see_actors();
		}
		if (0) see_stage(), see_actors();
	}
	if (OC2) see_stage(), see_actors();

	/* If the flood reached a target rather than just filling up
	 * all reachable locations, follow the trail back to its source
	 * and then take the first step onto it */

	if (!searching) {
		do {
			adj = target;
			switch (char_at(adj)) {
			case 'v': target = go_down(adj); break;
			case '>': target = go_right(adj); break;
			case '<': target = go_left(adj); break;
			case '^': target = go_up(adj); break;
			default:
				stage[0][0] = '*';
				goto failsafe;
			}
			show_at(adj, '.');
			if (OC2) see_stage(), see_actors();
		}
		while (target.all != a->loc.all);
		a->loc = adj;
	}
	failsafe:

	/* Erase all the flood markers */

	for (union location *p = in_range_list; p < tail; p++) {
		show_at(*p, '.');
		if (0) see_stage(), see_actors();
	}

	show_for(a, a->team);
	if (OC1) see_stage(), see_actors();
	return searching;
}



/* Enough messing about, get on with it */

int battle(char pathname[], int elf_power) {
	int error, rounds = 0, points;
	error = build_world(pathname, elf_power);

	/* Play rounds until combat ends */

	if (!error && actors < new_actor) for (;; rounds++) {

		/* Each actor takes a turn */

		for (struct actor *a = actors; a < new_actor; a++) {
			if (!a->dead) {
				show_for(a, '@');
				struct actor *enemy;
				if (enemy = enemy_in_range(a)) {
					if (error = attack(a, enemy)) goto combat_over;
				}
				else switch(approach_enemy(a)) {
				case NO_ENEMIES:
					goto combat_over;
				case NO_ENEMY:
					break;
				default:
					if (enemy = enemy_in_range(a)) {
						if (error = attack(a, enemy)) goto combat_over;
					}
				}
				show_for(a, a->team);
			}
		}

		/* Put actors back into reading order and bury the dead. */

		sort_actors();
		while (new_actor > actors && new_actor[-1].dead) new_actor--;
		
		if (OC1) see_stage(), see_actors();
	}

combat_over:
	if (OC1) see_stage(), see_actors();
	points = 0;
	for (struct actor *a = actors; a < new_actor; a++) {
		if (!a->dead) points += a->hit_points;
	}
	if (OC1) {
		printf("---\n\n\n\n\n\n\nelf power: %d\nerror: %d\nrounds: %d\npoints: %d\noutcome: %d\n",
			elf_power, error, rounds, points, rounds * points
		);
	}
	if (error) return -error;
	else return rounds * points;
}



int main(int argc, char *argv[]) {
	char *pathname = argc > 1? argv[1]: "input.txt";
	int loses_below = 4;
	int wins_at_or_above = VAL_MAX(((struct actor *)0)->attack_power);
	int elf_power = wins_at_or_above;
	int last_winning_result = 0;

	/* Make sure maximum representable attack power really is enough */

	int result = battle(pathname, elf_power);
	if (result < 0) {
		printf("Can't win at maximum attack power %d\n", elf_power);
		return -result;
	}

	/* Keep halving the gap between the losing and winning bounds
	 * until a definitive result is obtained. */

	while (wins_at_or_above > loses_below) {
		elf_power = (loses_below + wins_at_or_above) / 2;
		result = battle(pathname, elf_power);
		if (result < 0) loses_below = elf_power + 1;
		else {
			wins_at_or_above = elf_power;
			last_winning_result = result;
		}
	}
	printf("%d\n", last_winning_result);
	return 0;
}